Problem in the implementation of malloc function from scratch

Question

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 .

Out of your problem how do you will know which blocks are still useful and which ones are not ? What kind of garbage do you plan to implement, counters ? mark and sweep ? Stop and copy ? incremental ? ... Out of counters how do you will access to the pointers to the blocks saved in the stack(s) more the global variables more the registers and from them go through recursively inside the structures containing themselves pointers etc to mark them useful ? Do you implement your own compiler ? Do you will rewrite all the libs using allocation ? — bruno
– bruno, Commented Jun 14, 2019 at 13:34
the malloc is just in the introduction of the GC tutorial, i wanted to understand the forumla before moving on .. and i made it clear in the title : problem in the implementation of the malloc function ! the garbage collector is just the bigger thing i wanna do ! — HADDADI
– HADDADI, Commented Jun 14, 2019 at 13:44
I would recommend never using expressions like “as you can understand”. If something is obvious enough, you don't need to say it. If you're saying it, you do not really think it's obvious. Here “the alloc_size variable is the memory blocks we want to allocate” is wrong: alloc_size is the number of bytes that the caller is requesting. The fact that this is a number of bytes, but that malloc allocates blocks the size of which is a multiple of sizeof(header_t), is the reason for the formula (alloc_size + sizeof(header_t) - 1) / sizeof(header_t) + 1. — Pascal Cuoq
– Pascal Cuoq, Commented Jun 14, 2019 at 13:50
(alloc_size + sizeof(header_t) - 1) / sizeof(header_t) is “just enough words to provide the requested number of bytes”. + 1 is for the room occupied by header itself. This expression is a number of words (each word being of size sizeof(header_t)). — Pascal Cuoq
– Pascal Cuoq, Commented Jun 14, 2019 at 13:51
If this is a question only about a malloc implementation, why is a garbage collector relevant and used in the title? — KamilCuk
– KamilCuk, Commented Jun 14, 2019 at 13:53

Gerhardh · Accepted Answer · 2019-06-14 13:40:26Z

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.

Collectives™ on Stack Overflow

Problem in the implementation of malloc function from scratch

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related