CODEWITHSUNDEEP
c
HADDADI
HADDADI

Reputation: 72

Problem in the implementation of malloc function from scratch

So i was thinking about making my own garbage collector in C language and i've come across this tutorial that starts with the implementation of malloc function from scratch. The idea of the tutorial is to have a linked list of free blocks of memory, and whenever u use the malloc, it checks that list and gives u memory u want:

typedef struct header {
    unsigned int    size;
    struct header   *next;
} header_t;

{
    size_t num_units;
    header_t *p, *prevp;

    num_units = (alloc_size + sizeof(header_t) - 1) / sizeof(header_t) + 1; 

.....
}

The alloc_size variable, is the memory blocks we want to allocate; the num_units variable is the number of "nodes" of the lists you will have. My problem is with the formula they used , i understood the idea of (alloc_size) / sizeof(header_t) but why they added the sizeof(header_t) - 1 & the +1 .

Upvotes: 0

Views: 125

Answers (1)

Gerhardh
Gerhardh

Reputation: 12404

That is a common mechanism to round up to the next multiple value of a given value.

Integer division is simply dropping any fractional part, i.e. it rounds down.

This means

alloc_size / unit_size

would result in the exact number of units (if remainder is 0) or in 1 unit less (in all other cases).

Example:

   8 / 4 => 2  OK  |   ( 8 + (4-1)) / 4 == 11/4 => 2  OK
   9 / 4 => 2 NOK  |   ( 9 + (4-1)) / 4 == 12/4 => 3  OK
  10 / 4 => 2 NOK  |   (10 + (4-1)) / 4 == 13/4 => 3  OK
  11 / 4 => 2 NOK  |   (11 + (4-1)) / 4 == 14/4 => 3  OK
  12 / 4 => 3  OK  |   (12 + (4-1)) / 4 == 15/4 => 3  OK

Simply adding 1 to the result would mean wasting 1 unit whenever the size already is a multiple.

Finally they add another +1 to have space for the header itself.

Thus you are allocating size for 1 header_t used to store information about the allocated block + the memory for the allocation request itself.

Upvotes: 2

Related Questions