A confusion at heap_mark_blocks_taken() function in heap.c

[monzurularash]

I have a confusion about a function at heap.c. Does following line at function heap_mark_blocks_taken() has "off by one" error?

if (i != end_block -1) { entry |= HEAP_BLOCK_HAS_NEXT; }

Should it be following instead:

if (i != end_block ) { entry |= HEAP_BLOCK_HAS_NEXT; }

/*

for example: if total_block =4 and start_blok =0, so end_block=3

so we want to mark(set) the block0, block1 and block2 with flag HAS_NEXT.

*/

[nibblebits]

This looks like the case, I will look into this further and update this thread in the next few weeks.

[chemistr33]

I think the original code from the instructor was correct. If you remove the - 1, you'll incorrectly mark the last block in a sequence as being Taken | Has-Next.

GDB Log of heap_mark_blocks_taken() function

Breakpoint 3, heap_mark_blocks_taken (heap=0x103028 <kernel_heap>, start_block=0, total_blocks=5) at ./src/memory/heap/heap.c:387 387 { 389 int end_block = (start_block + total_blocks) - 1; 392 HEAP_BLOCK_TABLE_ENTRY entry 396 if (total_blocks > 1) $22 = 4 // print end_block $23 = 0 // print start_block $24 = 5 // print total_blocks 398 entry |= HEAP_BLOCK_HAS_NEXT; 403 for (int i = start_block; i <= end_block; i++) 405 heap->table->entries[i] = entry; 406 entry = HEAP_BLOCK_TABLE_ENTRY_TAKEN; $25 = 193 '\301' // print heap->table->entries[i] , First|Taken|Has-next block 407 if (i != end_block - 1) 409 entry |= HEAP_BLOCK_HAS_NEXT; 403 for (int i = start_block; i <= end_block; i++) 405 heap->table->entries[i] = entry; 406 entry = HEAP_BLOCK_TABLE_ENTRY_TAKEN; $26 = 129 '\201' // print heap->table->entries[i] , Taken|Has-next block 407 if (i != end_block - 1) 409 entry |= HEAP_BLOCK_HAS_NEXT; 403 for (int i = start_block; i <= end_block; i++) 405 heap->table->entries[i] = entry; 406 entry = HEAP_BLOCK_TABLE_ENTRY_TAKEN; $27 = 129 '\201' // print heap->table->entries[i] , Taken|Has-next block 407 if (i != end_block - 1) 409 entry |= HEAP_BLOCK_HAS_NEXT; 403 for (int i = start_block; i <= end_block; i++) 405 heap->table->entries[i] = entry; 406 entry = HEAP_BLOCK_TABLE_ENTRY_TAKEN; $28 = 129 '\201' // print heap->table->entries[i] , Taken|Has-next block 407 if (i != end_block - 1) 403 for (int i = start_block; i <= end_block; i++) 405 heap->table->entries[i] = entry; 406 entry = HEAP_BLOCK_TABLE_ENTRY_TAKEN; $29 = 1 '\001' // print heap->table->entries[i] , Taken block qemu-system-i386: QEMU: Terminated via GDBstub [Inferior 1 (process 1) killed]

Key observation

As you step through the for-loop, the value of the heap->table->entries[i], for 5 blocks progresses like:

[193] [129] [129] [129] [1] <- entry values in decimal [FTH] [TH] [TH] [TH] [T] <- entry attributes [0] [1] [2] [3] [4] <- indices