malloc address alignment (K&R2 exercise) 
Author Message
 malloc address alignment (K&R2 exercise)

I was recently looking at the sample malloc/free implementation in K&R2.
While most of it seems fairly straightforward, I'm at a loss as to how to
solve the book's last exercise, which is to write a routine that allows a
user, at any time, to add any static or external array into the list
maintained by malloc. The fundamental concept that I'm lacking is how to
guarantee the address alignment is compatible with the rest of the free
list, in a reasonably machine independent fashion. Given the sample malloc
header struct (slightly paraphrased from the text):

typedef long Align;

typedef union header {
  struct {
    union header *next; /* next free block, if on free list */
    unsigned size;      /* size of this block */
  } s;
  Align dummy;

Quote:
} Header;

My initial implementation naively ignores the issue of alignment:

void bfree(void *mem, unsigned size){
  Header *p= mem;

  if(size >= sizeof(Header)){
    p->s.size= size - sizeof(Header);
    free(p + 1);
  }

Quote:
}

However, I suspect that the above routine would break horribly if I
suppose that sizeof(Foo) < sizeof(Align), and that I have an array of e.g.
25 Foos which I would like to free with it. How can I make sure that I can
safely put an Align in the same area of memory?

TIA for any tips.
Tristan Miller (self-instructing student of C)



Sat, 14 Jul 2001 03:00:00 GMT  
 malloc address alignment (K&R2 exercise)


Quote:
> I was recently looking at the sample malloc/free implementation in K&R2.
> While most of it seems fairly straightforward, I'm at a loss as to how to
> solve the book's last exercise, which is to write a routine that allows a
> user, at any time, to add any static or external array into the list
> maintained by malloc. The fundamental concept that I'm lacking is how to
> guarantee the address alignment is compatible with the rest of the free
> list, in a reasonably machine independent fashion. Given the sample malloc
> header struct (slightly paraphrased from the text):

> typedef long Align;

> typedef union header {
>   struct {
>     union header *next; /* next free block, if on free list */
>     unsigned size;      /* size of this block */
>   } s;
>   Align dummy;
> } Header;
> ...
> However, I suspect that [naive impl] would break horribly if
> ... sizeof(Foo) < sizeof(Align), and I [pass an array of Foo].

Actually the alignment requirement might not be the same as
the size of a primitive type.  But it doesn't matter here.  

If pointers are implemented such that casting to a (large enough)
integral type gives the address, and all alignments are (small)
powers of two -- which are not guaranteed by the standard,
but usual on most CPUs/compilers that you are likely to encounter
-- then even if a supplied block is not sufficiently aligned
you can look for a portion of it that is:

#define ALIGNMASK (sizeof Align - 1)

  size_t bias; /* actually will be only up to maybe 15 */

  if( (bias = (size_t)mem & ALIGNMASK) !=0 ){
    if( size < sizeof Align - bias )
      /* not enuf room to adjust, discard or reject */
    mem += sizeof Align - bias;
    size -= sizeof Align - bias;
  }
  /* now the (smaller) chunk mem,size is maximally aligned */

If the maximum alignment (described by Align) is larger than
the size (and alignment) of s, and your malloc/free allow a
freelist element to be only aligned as s while the body must be
aligned as Align for return from malloc, you can be even trickier.  

(posted and mailed) David.Thompson at but not for trintech.com



Fri, 27 Jul 2001 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. New K&R2 exercise: fix getint

2. K&R2 Exercise 5.17- Field Sort

3. Newbie: Question about K&R2 Exercise 1-21

4. K&R2 exercise 1-18

5. Exercises in K&R2

6. K&R2 bug: malloc code

7. K&R1 vs. K&R2

8. Newbie getting runtime Exception (STATUS_ACCESS_VIOLATION) trying to implement Ex. 2-4 from K&R2

9. K&R2's implicit declaration of exit()

10. Address alignment and qsort()

11. Have K&R2, looking for simpler resource on pointers

12. In the reference manual of K&R2 (2)

 

 
Powered by phpBB® Forum Software