Malloc Assignment

NEWMALLOC AND NEWFREE ALGORITHM

This will implement an alternate version of malloc and free. For demonstration purposes a character array of 50,000 will be used as the memory to be allocated. Out of that the first 12 bytes will be used as the storage space for the header, which will be the starting point of the linked list storing the allocated nodes.

Each node will have 3 attributes

• Next – The pointer to the next node
• Size – The size requested by the caller
• Address – the array cell value in which the node begins

NewMalloc

NewMalloc will require the number of bytes that needs to be allocated to be passed. Then it will search for the first suitable location for the new node to be inserted. When the sufficient amount of continuous space is found the node will be inserted at that point.

If this is at the end of the linked list the new node will be simply inserted as the last node of the linked list and if it is in between two nodes, the links will be adjusted appropriately and the new node will be inserted.

The allocation uses the first fit basis.

FIRST FIT

First fit is when the node will be inserted at the first available spot. The search will stop when a continuous amount of free array cells are available big enough for the node head and the space requested by the caller. There may be spaces which are much more suitable later in the array, but this will ignore that.

This was chosen because mainly if best fit was selected it will spend a large amount of time looking for the best location in many iterations. Best fit will search the array for space that is equal to the requirement, and then one more than the requirement and so on until the necessary array space is found. This will require many iterations in most cases which will simply be a waste of time. So for increased efficiency first fit was chosen.

NewFree

The freeing method will simply identify the node to which the pointer refers to, and then remove it from the array. If the node is at the end of the linked list it will simply set the previous node as the linked list’s end. If it is in between two nodes the node will be removed linking the previous and next nodes together.

This algorithm will not maintain a separate linked list for free nodes. The free spaces available between nodes will be calculating the difference of the node pointers. This will eliminate internal fragmentation thus a need for defragmentation will not exist.

NEWMALLOC AND NEWFREE CODE

The code segment will contain only the Newmalloc and NewFree fucntions. the main function will need to be added.

The header part needs to be in a separate file named myheader.h

HEADER-

#ifndef _header_
#define _header_

void *NewMalloc(size_t);
void NewFree(void *);

#endif

CODE-

#include <sys/time.h>
#include <stdio.h>
#include "myheader.h"

#define MAXMALLOCSIZE 100
#define MAXMALLOC 10

void *myMalloc(size_t);
void myFree(void *);
void* insert(size_t,node *);
void print();


int main () {

    void  *ptr[MAXMALLOC] = {NULL};
    int i;
    while (1) {
        for (i=0;i<MAXMALLOC;i++){
            int r = random()%2;
            if (r==0){
                if (ptr[i]!=NULL){
                    myFree(ptr[i]);
                    ptr[i] = NULL;
                } else {
                    size_t t = random()%MAXMALLOCSIZE;
                    char *c = myMalloc(t);
                    ptr[i] = (void *) c;
                    if (ptr[i] == NULL) {
                        printf("not enough space!\n");
                        return 0;
                    }
                    //printf("writing %lu\n",t);
                    while (t>0){
                        *c = 0xFF;
                        c++;
                        t--;
                    }
           
                }
            }
        }
    }
    return 0;
}


void *myMalloc(size_t size){
    initialize();
    char *address;
    int check=1;
    //check if array size is exceeded
    if( size+12 > 1000){
        printf("Cannot allocate memory\n");   
        return NULL;
    }else{
       
        node* temp;
        temp=(node *) full_head;
       
        while((*temp).next!=NULL && check==1){
            printf("aawa\n");
            //check if free space available between allocated nodes
            int x1=(int)(*temp).next-(int)temp;
            int x2=(*temp).size+size+24;
            if(x1>x2){
                printf("allocate : %d\n",size);
                address=insert(size,temp);
                check=0;
            }
            temp=(*temp).next;
        }
       
        //check if remaining nodes enough to allocate
        if(check==1 && (int)temp-(int)full_head+(*temp).size+size+12<1000){
            address=insert(size,temp);
        }
       
        return address;
    }
}

void *insert(size_t size, node* current){
    node *temp;
    //calculate relavant array cell
    int position=((int)current)-((int)full_head)+(*current).size+12;
   
    temp=(node*)&array[position];
    (*temp).address=position;
   
    if((*current).next!=NULL){
        node *next = (*current).next;
        (*current).next=temp;
        (*temp).next=next;
        (*temp).size=size;
    }else{
        (*current).next=temp;
        (*temp).size=size;
        (*temp).next=NULL;
    }
   
    position= position+12;
    printf("Node created\n");
    return &array[position];
}

void myFree(void *ptr){
    if(ptr== NULL){
        printf("NULL pointer\n");
    }else if(ptr < 0){
        printf("Irrelavant pointer\n");
    }else{
        //check=0 means that there are no nodes connected
        //check=1 means that there are nodes connected to the header
        int check=0;
        int position = (int)ptr-(int)full_head-12;
               
        node* temp;
        node* prev;
        temp=(node *) full_head;
       
        while((*temp).next!=NULL && (*temp).address!=position){
            check=1;
            prev=temp;
            temp=(*temp).next;
        }
       
        if(check==0){
            (*full_head).next=NULL;
        }else{
            printf("free position : %d\n",(*temp).address);
            node* next=(*temp).next;
            (*prev).next=next;
        }
    }
}

void print(){
    node* temp;
    temp=(node *) full_head;
       
    while((*temp).next!=NULL){
        printf("start : %d\n",(*temp).address);
        printf("size : %d\n", (*temp).size);
        printf("end : %d\n\n",(*temp).address+(*temp).size+12);
        temp=(*temp).next;
    }
    printf("start :%d\n",(*temp).address);
    printf("size : %d\n", (*temp).size);
    printf("end : %d\n\n",(*temp).address+(*temp).size+12);
    printf("---------------------------------------------------------\n");
}

Shell alternate implementation in C

Introduction

This is the code in which a alternate shell is implemented.


This version of shell is implemented at the very basic level and  does not have the following features.

• cd command
• " " when accessing files and folder 

These features will be implemented in future versions.

Important to remember when operating :

• To set environmental path variable type 'PATH' which will then ask you to type in the path separately. This will not replace the $PATH variable contents but append to its content.
• To exit mosh type 'exit'

The Algorithm

First this will read the user command character by character. When the user inputs a command, the last letter or rather the last character will be a enter character (\n). So first this character will be replaced by a null character.This will be helpful especially when searching for the end of the command.

Then it will check for any sign of a pipe command. A character by character search is done and if '|' is found inside the command then it will be split into two arrays from that point onwards. This is to make sure that two different arrays can be passed into the child and parent processes.

Then the characters in the array or arrays will be tokenized using the space ( this will break the characters into words) and store the tokenized characters (separate words) into an array. Then simply depending on if its a pipe command or not it will be passed to the relevant execution methods.

The Code

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>

char cmd[50];
char cmd2[50];
char *retrn[10];
char *retrn2[10];
int control=1;


//---------------------------------------------------------------------
main()
{
    printf("\n\n\n ------------ ");
    printf(" My Own SHell ");
    printf(" ------------ \n\n\n");
    readInput();
}
//-----------------------------------------------------------------------
keep(){
    if (control==1 || control ==0){
        if(fork()){
            wait();
            readInput();
        }else{
            if (control==1)
                command();
            else if(control==0)
                pipe_command();
        }
    }else{    
        if(control==4){
            set_path();
        }
        else     if (control ==3)
                printf("MOSH will now exit. \n\n");   
            else
                readInput();
    }
   
}

//-----------------------------------------------------------------------

readInput(){
    memset(&cmd[0], 0, sizeof(cmd));
    memset(&cmd2[0], 0, sizeof(cmd2));
    control = 1;
    printf("\n[ MOSH ] $ ");
    if ( fgets(cmd, sizeof cmd, stdin) != NULL ){
        //remove the newline after each line
        char *newline = strchr(cmd, '\n');
        if ( newline != NULL ){
            *newline = '\0';
        }
        //serach for | and determine pipe commands
       
        char *pipe = strchr(cmd, '|');
        if( pipe != NULL){
            control=0;
            // split array and store commands after | into second array
            *pipe= '\0';
            pipe=pipe+1;
            strcpy(cmd2,pipe);
        }
    }

   
       
        int count=0;
        char delims[] = " ";
        char *result = NULL;
        result = strtok( cmd, delims );
        // look for command exit
        if(strcmp(cmd,"exit") == 0)
            control=3;
        //look for path setting command
        if(strcmp(cmd,"PATH") == 0)
            control=4;
        while( result != NULL ) {
             retrn[count]=result;
                result = strtok( NULL, delims );
            count+=1;
        }
        count=0;
        result = strtok( cmd2, delims );
        while( result != NULL ) {
             retrn2[count]=result;
                result = strtok( NULL, delims );
            count+=1;
    }
    keep();
}

//-----------------------------------------------------------------------

command(){       
    execvp(retrn[0],retrn);
}

//-----------------------------------------------------------------------

pipe_command(){
    //execute pipe command
    int pfds[2];
    pipe(pfds);
    if (!fork()) {
        close(1);      
        dup(pfds[1]);  
        close(pfds[0]);
        execvp(retrn[0],retrn);
    } else {
        close(0);     
        dup(pfds[0]);  
        close(pfds[1]);
        execvp(retrn2[0],retrn2);
    }   
}

//-----------------------------------------------------------------------
set_path(){
    char* pathvar=getenv("PATH");;
    printf("          Enter Path variable : ");
    fgets(cmd, sizeof cmd, stdin);
    char* path=malloc(sizeof(char)* (strlen(pathvar)+strlen(cmd)+2));
    path=strcat(path,pathvar);
    path=strcat(path,":");
    path=strcat(path,cmd);
    path=strcat(path, "\0");
       setenv("PATH",path,1);
    free(path);
    readInput();
}
Hope you enjoy !!!! :D :D