6 Replies - 425 Views - Last Post: 12 February 2014 - 05:04 AM Rate Topic: -----

#1 odougs  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 13
  • Joined: 05-January 14

C generic linked list: Calling free() on invalid chunk

Posted 11 February 2014 - 12:47 AM

Hello,

I'm trying to implement some basic data structures in C. Below is some code for a generic singly-linked list. The code works fine for storing malloc'd objects, but adding a pointer to a non-malloc'd object is unsafe, because that memory cannot be free'd. This is pretty obvious, and not much of a problem: it wouldn't make sense to store a pointer to a location on the stack or global space in a persistent data structure.

However, this got me curious... is there any sort of way I could guard against a client code adding a pointer to non-malloc'd memory? As far as I know, there is no good way to get this information from a pointer. In fact, I can only think of two ways to do it, and both seem like absolutely awful ideas:

  • Write my own storage allocator which llist_t can query to see if a void * belongs to the allocator. Force all client code to use that allocator.
  • Assume that a void * is malloc'd iff it is within the known heap range for this machine.


Yuck.

My code doesn't need to be 100% idiot-proof; "DONT store non-malloc'd items" is a perfectly reasonable precondition for the add method. Especially considering that I am writing this as a learning exercise, and for my own use - not a library for others to use. But just out of curiosity, can anyone think of a way around this? Or better yet, a better way to implement the generic linked list in C?



typedef struct llist_node {
  struct llist_node * next;
  void * data;
} llist_node_t;

void ll_add (llist_t * me, void * item)
{
  llist_node_t * nnode = (llist_node_t*) malloc (sizeof(llist_node_t));
  if (nnode == NULL) {
    printf ("malloc error\n");  //placeholder for real error handling routine
    exit(0);
  }

  nnode->data = item;

  if (me->lsize == 0)
    me->first = me->last = nnode;
  else {
    me->last->next = nnode;
    me->last = nnode;
  }
  me->lsize++;
}

void ll_del (llist_t * me, unsigned  i)
{
//node_access traverses list, finds element[i]
  llist_node_t * del = node_access (me, i);
  free (del->data);
  free (del);
  me->lsize--;
}



Is This A Good Question/Topic? 0
  • +

Replies To: C generic linked list: Calling free() on invalid chunk

#2 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1112
  • View blog
  • Posts: 4,619
  • Joined: 09-June 09

Re: C generic linked list: Calling free() on invalid chunk

Posted 11 February 2014 - 01:40 AM

The safest way is to take the responsibility out of the clients hands and you malloc memory for everything that is passed to the add function. Your add function should not be concerned where the memory is allocated (stack, or heap), it should allocate memory for it an memcpy it to the list.

e.g.
void ll_add (llist_t * me, void * item, int bytes)
{
  llist_node_t * nnode = (llist_node_t*) malloc (sizeof(llist_node_t));
  
  if (nnode == NULL) {
    printf ("malloc error\n");  //placeholder for real error handling routine
    exit(0);
  }

  //nnode->data = item;
  nnode->data = malloc(bytes); //allocate memory for item
  memcpy(nnode->data, item, bytes); //copy memory to list

  if (me->lsize == 0)
    me->first = me->last = nnode;
  else {
    me->last->next = nnode;
    me->last = nnode;
  }
  me->lsize++;
}



There is no standard way of getting heap's and stack's address space. If you are on linux you can use sbrk to get the current heap pointer and use that to reference memory locations to determine where they are allocated. This is just an educational exercise, the best way of handling your linked list issue is in the code above, but here's a fun example of what I mentioned.

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

#define INIT_HEAP_START heap_start = sbrk(0)
void *heap_start;

int was_malloced(void *addr) {
   return addr >= heap_start && addr < sbrk(0);
}

int main() {
   INIT_HEAP_START;

   char buff[100];
   int *malloced = malloc(sizeof(int));

   printf("buff is allocated on %s\n", was_malloced(buff) ? "heap" : "stack");
   printf("malloced is allocated on %s\n", was_malloced(malloced) ? "heap" : "stack");

   return 0;
}


This post has been edited by jjl: 11 February 2014 - 02:31 AM

Was This Post Helpful? 1
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5937
  • View blog
  • Posts: 12,862
  • Joined: 16-October 07

Re: C generic linked list: Calling free() on invalid chunk

Posted 11 February 2014 - 06:48 AM

Your ll_del has issues, btw. You need to check if i==0 and remove the first properly. You also need to make sure the last is affected and if i is actually in range.

To be honest, if I gave a pointer to a list implementation, I would NEVER expect that list to free an element on me. That is above and beyond the job of a container object.

You could implement a flag on the node...
typedef struct llist_node_s {
	void *data;
	int free_data;
	struct llist_node_s *next;
} llist_node;

// just taking a pointer, not responsible for freeing it
void ll_add (llist *, void *);

// making a copy of the data, must free it
void ll_add_copy (llist *, void *, size_t);

void ll_node_free(llist_node *n) {
	if (n->free_data) { free (n->data); }
	free(n);
}


Was This Post Helpful? 1
  • +
  • -

#4 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3663
  • View blog
  • Posts: 11,482
  • Joined: 05-May 12

Re: C generic linked list: Calling free() on invalid chunk

Posted 11 February 2014 - 06:51 AM

Back in the 80's and 90's, the vogue was to roll your own memory allocator for C or C++, so your first option would have been considered not only acceptable, but de rigueur. If you did that now, most people would look at you funny because most modern runtime libraries have much more sophisticated memory allocation implementations.
Was This Post Helpful? 0
  • +
  • -

#5 odougs  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 13
  • Joined: 05-January 14

Re: C generic linked list: Calling free() on invalid chunk

Posted 11 February 2014 - 10:53 PM

View Postjjl, on 11 February 2014 - 01:40 AM, said:

The safest way is to take the responsibility out of the clients hands and you malloc memory for everything that is passed to the add function. Your add function should not be concerned where the memory is allocated (stack, or heap), it should allocate memory for it an memcpy it to the list.

e.g.
Spoiler



Looks to me like this is 'the right way' to do it! I feel a bit silly I didn't consider this, but I'm glad I asked... guess I was too focused on the issue of whether or not the client malloc'd to see the obvious solution that renders that question unecessary! Thanks for showing me that.


View Postjjl, on 11 February 2014 - 01:40 AM, said:

There is no standard way of getting heap's and stack's address space. If you are on linux you can use sbrk to get the current heap pointer and use that to reference memory locations to determine where they are allocated. This is just an educational exercise, the best way of handling your linked list issue is in the code above, but here's a fun example of what I mentioned.

Spoiler



This is very interesting; I am always eager to look at unorthodox code that can teach me more about how the system works. Once again I think this is better than the approach I had in mind, which is pretty primitive. I didn't actually implement it, but I was thinking something like:

void * heap_start;
int main()
{
  heap_start = malloc(1);
  ...
}
...
int was_mallocd (void * foo)
{
  int x = 0;
  void * stack_top = &x;
  
  return  (  (foo > heap_start && foo < stack_top)   //don't assume dir. of growth
          || (foo < heap_start && foo > stack_top))
}



...which is really ugly (and not strictly correct, since &x will be inside the uppermost frame), but I think it would work on "normal" architectures where the stack and heap grow towards each other with nothing in between. I am under the impression that just about all architectures do this, but I have only studied MIPS and x86, so I'm cautious and would be interested in any counterexamples.

(Actually, someone could abuse this approach by generating a pointer to a local in a higher stack frame, returning that pointer, and then calling was_mallocd(). Heh.)


View Postbaavgai, on 11 February 2014 - 06:48 AM, said:

Your ll_del has issues, btw. You need to check if i==0 and remove the first properly. You also need to make sure the last is affected and if i is actually in range.

To be honest, if I gave a pointer to a list implementation, I would NEVER expect that list to free an element on me. That is above and beyond the job of a container object.

You could implement a flag on the node...
Spoiler




Thanks for pointing that out - can't believe I posted that! Here is a better version; I'm curious to know what you think.

Spoiler



I get where you are coming from about letting the client do all memory allocation / deallocation calls. However I would much rather write one chunk of code that deallocates dead objects properly, so I never have to worry about it again. Otherwise, as a programmer working on client code, I would probably be very paranoid about how I use the list, which is going to reduce my productivity.
Was This Post Helpful? 0
  • +
  • -

#6 odougs  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 13
  • Joined: 05-January 14

Re: C generic linked list: Calling free() on invalid chunk

Posted 11 February 2014 - 11:12 PM

View PostSkydiver, on 11 February 2014 - 06:51 AM, said:

Back in the 80's and 90's, the vogue was to roll your own memory allocator for C or C++, so your first option would have been considered not only acceptable, but de rigueur. If you did that now, most people would look at you funny because most modern runtime libraries have much more sophisticated memory allocation implementations.


Interesting to hear that; I know a handful of details about programming & computer history, but have little sense of what it was really like back then (I'm fairly young). Sometimes I wonder if the older generations of programmers were tougher and better because they had more incentive (or even need) to figure out how such things work. But then again, the ease of access to free high-quality programming & CS resources we have today is pretty amazing. I suppose too much or too little of either can hinder a person's growth. Personally, I tend to try to figure out moderately difficult problems on my own whenever I have time, but rely on standard libraries for most of my code, especially if doing otherwise would slow me down a lot.
Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5937
  • View blog
  • Posts: 12,862
  • Joined: 16-October 07

Re: C generic linked list: Calling free() on invalid chunk

Posted 12 February 2014 - 05:04 AM

View Postodougs, on 12 February 2014 - 12:53 AM, said:

I'm curious to know what you think.


Looks mostly good. You need check if the list is empty before you start. Also, you forgot to null the last->next. A list with one item is another edge case. ( You also forgot me-> in front of a couple of variables; guess you didn't compile this one? )

You can actually combine the end and middle, which might make things easier.

void ll_del(llist_t * me, unsigned i) {
	if (me->size>0) {
		llist_node_t *tmp;
		if (me->size==1) {
			tmp = me->first;
			me->first = me->last = NULL;
		} else if (i == 0) {
			tmp = me->first;
			me->first = tmp->next;
		} else {
			llist_node_t *prev = node_access(me, i - 1);
			tmp = prev->next;
			prev->next = tmp->next;
			if (i == me->size - 1) { me->last = prev; }
		}
		free(tmp->data);
		free(tmp);
		me->size--;
	}
}



Note, calling node_access(me, i - 1) often is making a strong case for a doubly linked list. Or, accessing values by index often would make a case for some other structure.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1