How to replace Malloc in linked list

Question

I am currently working on injecting faults and in one of the application I want to replace dynamic part(Malloc) and make it static, So that it is not dependent on kernel instructions. Here is the basic linked list program. How do I replace Malloc instruction and still make liked list to work.

struct test_struct* create_list(int val)
{
    printf("\n creating list with headnode as [%d]\n",val);    

    struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));

    if(NULL == ptr1)
    {   
        printf("\n Node creation failed \n");
        return NULL;
    }

    ptr1->val = val;
    ptr1->next = NULL;
    head = curr = ptr1;
    return ptr1;
}

How will you make a linked list using a satic symbol? it doesn't make much sense to me. You will have only one symbol in the end. And what you mean with "So that it is not dependent on kernel instructions. " ? — The Mask, May 25 '14 at 00:56
You could have a preset pool of structs, and some flags to show which ones are currently in use. Replace 'malloc' with finding one that's not in use; and replace 'free' wuth resetting the flag on an in-use one. — M.M, May 25 '14 at 01:19
@TheMask I am working on fault injector. That injects faults in the instructions register contents. If any exception is generated I have application level handler but When the fault is injected in the malloc assembly part the kernel is dealing with signals not the application exception handler. — Pavan Kangokar, May 25 '14 at 01:56
@MattMcNabb: Can you please elaborate more Thank you very much — Pavan Kangokar, May 25 '14 at 01:57
@Anonymous The other question is about how to implement `malloc` using a standard OS-level dynamic allocation primitive such as `sbrk`. This one is about implementing linked lists without allocating memory dynamically (as far as the system is concerned) at all. While it may still be a duplicate of some SO question, it's not a duplicate of the one you linked to. — user4815162342, May 25 '14 at 08:11
@user4815162342 I think it's 99% a dupe, since they're both essentially "how do I implement free/malloc". Replacing sbrk with a static block of memory is a trivial modification I think. — Paul Hankin, May 25 '14 at 09:57
@Anonymous I don't see how it is a duplicate. The older question is about implementing malloc, this one is about removing dynamic allocation from a specific data structure. Reimplementing `malloc` is only *one* way to resolve the latter, and not a very good one at that. Marking it as a duplicate (and without due process of 5 cast votes, AFAICT) is wrong, and non-courteous to the submitter. — user4815162342, May 25 '14 at 12:35

M.M · Answer 1 · 2014-05-25T08:10:16.937

You can write your own malloc/free using a fixed-size pool, for example:

typedef struct test_struct T;
#define POOL_SIZE 100
static bool pool_use[POOL_SIZE] = { 0 };
static T pool[POOL_SIZE];

T *t_malloc(void)
{
    for (int ii = 0; ii < POOL_SIZE; ++ii)
        if ( !pool_use[ii] )
        {
            pool_use[ii] = 1;
            return &pool[ii];
        }

    return NULL;
}

void t_free(T *t)
{
    for (int ii = 0; ii < POOL_SIZE; ++ii)
        if ( t == &pool[ii] )
        {
             pool_use[ii] = 0;
             break;
        }
}

Note: This is just a basic example to illustrate the idea of a memory pool. It could be optimized a lot. There's a lot of theory around about allocators and memory pools (it's the sort of thing you could write a thesis on if doing postgrad work for a comp sci degree).

If your application is going to depend on the speed and/or space-efficiency of this allocator then you could do a bit more research about what techniques are available.

You're right, but it might still be a good idea to at least point out the flaw, so that a future reader doesn't copy it into her code, thinking it's a viable solution. (I deleted the original comment because my idea with using two stacks wouldn't in fact work.) — user4815162342, May 25 '14 at 08:07

How to replace Malloc in linked list

1 Answers1