In this example, a heap with 1534 words is created, followed by
aaa = malloc(30)
bbb = malloc(4)
ccc = malloc(16)
ddd = malloc(6)
eee = malloc(3)
fff = malloc(4)
free(eee)
free(ddd)
free(ccc)
free(bbb)
free(fff)
free(aaa)
zzz = malloc(1000)
yyy = malloc(4) attempted but fails.
rabbit ~ $ CC buddysystem.cpp
rabbit ~ $ a.out
level max_data_size memory_occupied_by_chunk 045
1 10 11
2 22 23
3 46 47 4 94 95
5 190
6 382
7 766
8 1534
Just type
name size
free address
0: 1534 words, FREE
> aaa 30
191 383 767
1535
to allocate memory
to free memory
requested allocation of 30 words for ‘aaa’
will have to use a level 3 chunk of capacity 46 words
at level 8, checking chunk starting at 0
a free chunk that must be split
created new chunk at 1, size 766
created new chunk at 768, size 766
at level 7, checking chunk starting at 1
a free chunk that must be split
created new chunk at 2, size 382
created new chunk at 385, size 382
at level 6, checking chunk starting at 2
a free chunk that must be split
created new chunk at 3, size 190
created new chunk at 194, size 190
at level 5, checking chunk starting at 3
a free chunk that must be split
created new chunk at 4, size 94
created new chunk at 99, size 94
at level 4, checking chunk starting at 4
a free chunk that must be split
created new chunk at 5, size 46
created new chunk at 52, size 46
at level 3, checking chunk starting at 5
a free chunk of the right size
retagging chunk 4, split with availability 46
retagging chunk 3, split with availability 94 46
retagging chunk 2, split with availability 190 94 46
retagging chunk 1, split with availability 382 190 94 46
retagging chunk 0, split with availability 766 382 190 94 46
successful
0: available sizes: 766 382 190 94 46
| 1: available sizes: 382 190 94 46
| | 2: available sizes: 190 94 46
| | | 3: available sizes: 94 46
| | |
| | |
| | |
| | |
| | | 194: 190 words, FREE
| | 385: 382 words, FREE
| 768: 766 words, FREE
| 4: available sizes: 46
| | 5:46words,USEDbyaaa | | 52:46words,FREE
| 99:94words,FREE
> bbb 4
requested allocation of 4 words for ‘bbb’
will have to use a level 0 chunk of capacity 4 words
at level 8, checking chunk starting at 0
a split chunk, availability: 766 382 190 94 46
at level 7, checking chunk starting at 1
a split chunk, availability: 382 190 94 46
at level 6, checking chunk starting at 2
a split chunk, availability: 190 94 46
at level 5, checking chunk starting at 3
a split chunk, availability: 94 46
at level 4, checking chunk starting at 4
a split chunk, availability: 46
at level 3, checking chunk starting at 52
a free chunk that must be split
created new chunk at 53, size 22
created new chunk at 76, size 22
at level 2, checking chunk starting at 53
a free chunk that must be split
created new chunk at 54, size 10
created new chunk at 65, size 10
at level 1, checking chunk starting at 54
a free chunk that must be split
created new chunk at 55, size 4
created new chunk at 60, size 4
at level 0, checking chunk starting at 55
a free chunk of the right size
retagging chunk 54, split with availability 4
retagging chunk 53, split with availability 10 4
retagging chunk 52, split with availability 22 10 4
retagging chunk 4 as split with availability 22 10 4
retagging chunk 3 as split with availability 94 22 10 4
retagging chunk 2 as split with availability 190 94 22 10 4
retagging chunk 1 as split with availability 382 190 94 22 10 4
retagging chunk 0 as split with availability 766 382 190 94 22 10 4
successful
0: available sizes: 766 382 190 94 22 10 4
| 1: available sizes: 382 190 94 22 10 4
| | 2: available sizes: 190 94 22 10 4
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | 385: 382 words, FREE
| 768: 766 words, FREE
| 3: available sizes: 94 22 10 4
| | 4:availablesizes:22104
| | | 5:46words,USEDbyaaa
| | | 52:availablesizes:22104
| | | | 53:availablesizes:104
| | | | | 54:availablesizes:4
| | | | | | 55:4words,USEDbybbb | | | | | |60:4words,FREE
| | | | | 65:10words,FREE
| | | | 76:22words,FREE
| | 99:94words,FREE
| 194: 190 words, FREE
> ccc 16
requested allocation of 16 words for ‘ccc’
will have to use a level 2 chunk of capacity 22 words
at level 8, checking chunk starting at 0
a split chunk, availability: 766 382 190 94 22 10 4
at level 7, checking chunk starting at 1
a split chunk, availability: 382 190 94 22 10 4
at level 6, checking chunk starting at 2
a split chunk, availability: 190 94 22 10 4
at level 5, checking chunk starting at 3
a split chunk, availability: 94 22 10 4
at level 4, checking chunk starting at 4
a split chunk, availability: 22 10 4
at level 3, checking chunk starting at 52
a split chunk, availability: 22 10 4
at level 2, checking chunk starting at 76
a free chunk of the right size
retagging chunk 52 as split with availability 10 4
retagging chunk 4 as split with availability 10 4
retagging chunk 3 as split with availability 94 10 4
retagging chunk 2 as split with availability 190 94 10 4
retagging chunk 1 as split with availability 382 190 94 10 4
retagging chunk 0 as split with availability 766 382 190 94 10 4
successful
0: available sizes: 766 382 190 94 10 4
| 1: available sizes: 382 190 94 10 4
| | 2: available sizes: 190 94 10 4
| | | 3: available sizes: 94 10 4
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | 194: 190 words, FREE
| | 385: 382 words, FREE
| 768: 766 words, FREE
| 4: available sizes: 10 4
| | 5:46words,USEDbyaaa
| | 52:availablesizes:104
| | | 53:availablesizes:104
| | | | 54:availablesizes:4
| | | | | 55:4words,USEDbybbb | | | | |60:4words,FREE
| | | | 65:10words,FREE
| | | 76:22words,USEDbyccc
| 99:94words,FREE
> ddd 6
requested allocation of 6 words for ‘ddd’
will have to use a level 1 chunk of capacity 10 words
at level 8, checking chunk starting at 0
a split chunk, availability: 766 382 190 94 10 4
at level 7, checking chunk starting at 1
a split chunk, availability: 382 190 94 10 4
at level 6, checking chunk starting at 2
a split chunk, availability: 190 94 10 4
at level 5, checking chunk starting at 3
a split chunk, availability: 94 10 4
at level 4, checking chunk starting at 4
a split chunk, availability: 10 4
at level 3, checking chunk starting at 52
a split chunk, availability: 10 4
at level 2, checking chunk starting at 53
a split chunk, availability: 10 4
at level 1, checking chunk starting at 65
a free chunk of the right size
retagging chunk 53 as split with availability 4
retagging chunk 52 as split with availability 4
retagging chunk 4 as split with availability 4
retagging chunk 3 as split with availability 94 4
retagging chunk 2 as split with availability 190 94 4
retagging chunk 1 as split with availability 382 190 94 4
retagging chunk 0 as split with availability 766 382 190 94 4
successful
0: available sizes: 766 382 190 94 4
| 1: available sizes: 382 190 94 4
| | 2: available sizes: 190 94 4
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | 385: 382 words, FREE
| 768: 766 words, FREE
| 3: available sizes: 94 4
| | 4: available sizes: 4
| |
| |
| |
| |
| |
| |
| |
| |
| | 99:94words,FREE | 194: 190 words, FREE
| 5:46words,USEDbyaaa
| 52: available sizes: 4
| | 53:availablesizes:4
| | | 54:availablesizes:4
| | | | 55:4words,USEDbybbb | | | |60:4words,FREE
| | | 65:10words,USEDbyddd | | 76:22words,USEDbyccc
> eee 3
requested allocation of 3 words for ‘eee’
will have to use a level 0 chunk of capacity 4 words
at level 8, checking chunk starting at 0
a split chunk, availability: 766 382 190 94 4
at level 7, checking chunk starting at 1
a split chunk, availability: 382 190 94 4
at level 6, checking chunk starting at 2
a split chunk, availability: 190 94 4
at level 5, checking chunk starting at 3
a split chunk, availability: 94 4
at level 4, checking chunk starting at 4
a split chunk, availability: 4
at level 3, checking chunk starting at 52
a split chunk, availability: 4
at level 2, checking chunk starting at 53
a split chunk, availability: 4
at level 1, checking chunk starting at 54
a split chunk, availability: 4
at level 0, checking chunk starting at 60
a free chunk of the right size
retagging chunk 54 as split with availability none
retagging chunk 53 as split with availability none
retagging chunk 52 as split with availability none
retagging chunk 4 as split with availability none
retagging chunk 3 as split with availability 94
retagging chunk 2 as split with availability 190 94
retagging chunk 1 as split with availability 382 190 94
retagging chunk 0 as split with availability 766 382 190 94
successful
0: available sizes: 766 382 190 94
| 1: available sizes: 382 190 94
| | 2: available sizes: 190 94
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | 385: 382 words, FREE
| 768: 766 words, FREE
| 3: available sizes: 94
| | 4: available sizes: none
| | | 5:46words,USEDbyaaa | | | 52: available sizes: none
| | |
| | |
| | |
| | |
| | |
| | | | 76:22words,USEDbyccc | | 99:94words,FREE
| 194: 190 words, FREE
| 53: available sizes: none
| | 54:availablesizes:none
| | | 55:4words,USEDbybbb | | | 60:4words,USEDbyeee | | 65:10words,USEDbyddd
> fff 4
requested allocation of 4 words for ‘fff’
will have to use a level 0 chunk of capacity 4 words
at level 8, checking chunk starting at 0
a split chunk, availability: 766 382 190 94
at level 7, checking chunk starting at 1
a split chunk, availability: 382 190 94
at level 6, checking chunk starting at 2
a split chunk, availability: 190 94
at level 5, checking chunk starting at 3
a split chunk, availability: 94
at level 4, checking chunk starting at 99
a free chunk that must be split
created new chunk at 100, size 46
created new chunk at 147, size 46
at level 3, checking chunk starting at 100
a free chunk that must be split
created new chunk at 101, size 22
created new chunk at 124, size 22
at level 2, checking chunk starting at 101
a free chunk that must be split
created new chunk at 102, size 10
created new chunk at 113, size 10
at level 1, checking chunk starting at 102
a free chunk that must be split
created new chunk at 103, size 4
created new chunk at 108, size 4
at level 0, checking chunk starting at 103
a free chunk of the right size
retagging chunk 102, split with availability 4
retagging chunk 101, split with availability 10 4
retagging chunk 100, split with availability 22 10 4
retagging chunk 99, split with availability 46 22 10 4
retagging chunk 3 as split with availability 46 22 10 4
retagging chunk 2 as split with availability 190 46 22 10 4
retagging chunk 1 as split with availability 382 190 46 22 10 4
retagging chunk 0 as split with availability 766 382 190 46 22 10 4
successful
0: available sizes: 766 382 190 46 22 10 4
| 1: available sizes: 382 190 46 22 10 4
| | 2: available sizes: 190 46 22 10 4
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | 385: 382 words, FREE
| 768: 766 words, FREE
| 3: available sizes: 46 22 10 4
| | 4: available sizes: none
| | | 5:46words,USEDbyaaa | | | 52: available sizes: none
| | |
| | |
| | |
| | |
| | |
| | | | 76:22words,USEDbyccc
| | 99:availablesizes:4622104
| | | 100:availablesizes:22104
| | | | 101:availablesizes:104
| | | | | 102:availablesizes:4
| | | | | | 103:4words,USEDbyfff | | | | | |108:4words,FREE
| 53: available sizes: none
| | 54:availablesizes:none
| | | 55:4words,USEDbybbb | | | 60:4words,USEDbyeee | | 65:10words,USEDbyddd
| | | | | 113:10words,FREE | | | | 124:22words,FREE
| | | 147:46words,FREE
| 194: 190 words, FREE
> free 60
requested deallocation of chunk 60
looking for chunk 60 in chunk 0, at level 8
split chuck, left 1 to 767, right 768 to 1534
looking for chunk 60 in chunk 1, at level 7
split chuck, left 2 to 384, right 385 to 767
looking for chunk 60 in chunk 2, at level 6
split chuck, left 3 to 193, right 194 to 384
looking for chunk 60 in chunk 3, at level 5
split chuck, left 4 to 98, right 99 to 193
looking for chunk 60 in chunk 4, at level 4
split chuck, left 5 to 51, right 52 to 98
looking for chunk 60 in chunk 52, at level 3
split chuck, left 53 to 75, right 76 to 98
looking for chunk 60 in chunk 53, at level 2
split chuck, left 54 to 64, right 65 to 75
looking for chunk 60 in chunk 54, at level 1
split chuck, left 55 to 59, right 60 to 64
looking for chunk 60 in chunk 60, at level 0
found it, marking as free, size 4
retagging chunk 54, split with availability 4
retagging chunk 53, split with availability 4
retagging chunk 52, split with availability 4
retagging chunk 4, split with availability 4
retagging chunk 3, split with availability 46 22 10 4
retagging chunk 2, split with availability 190 46 22 10 4
retagging chunk 1, split with availability 382 190 46 22 10 4
retagging chunk 0, split with availability 766 382 190 46 22 10 4
successful
0: available sizes: 766 382 190 46 22 10 4
| 1: available sizes: 382 190 46 22 10 4
| | 2: available sizes: 190 46 22 10 4
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | 385: 382 words, FREE
| 768: 766 words, FREE
| 3: available sizes: 46 22 10 4
| | 4: available sizes: 4
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | | 147:46words,FREE | 194: 190 words, FREE
| 5:46words,USEDbyaaa
| 52: available sizes: 4
| | 53:availablesizes:4
| | | 54:availablesizes:4
| | | | 55:4words,USEDbybbb | | | |60:4words,FREE
| | | 65:10words,USEDbyddd
| | 76:22words,USEDbyccc 99:availablesizes:4622104
| 100:availablesizes:22104
| | 101:availablesizes:104
| | | 102:availablesizes:4
| | | | 103:4words,USEDbyfff | | | |108:4words,FREE
| | | 113:10words,FREE
| | 124:22words,FREE
> free 65
requested deallocation of chunk 65
looking for chunk 65 in chunk 0, at level 8
split chuck, left 1 to 767, right 768 to 1534
looking for chunk 65 in chunk 1, at level 7
split chuck, left 2 to 384, right 385 to 767
looking for chunk 65 in chunk 2, at level 6
split chuck, left 3 to 193, right 194 to 384
looking for chunk 65 in chunk 3, at level 5
split chuck, left 4 to 98, right 99 to 193
looking for chunk 65 in chunk 4, at level 4
split chuck, left 5 to 51, right 52 to 98
looking for chunk 65 in chunk 52, at level 3
split chuck, left 53 to 75, right 76 to 98
looking for chunk 65 in chunk 53, at level 2
split chuck, left 54 to 64, right 65 to 75
looking for chunk 65 in chunk 65, at level 1
found it, marking as free, size 10
retagging chunk 53, split with availability 10 4
retagging chunk 52, split with availability 10 4
retagging chunk 4, split with availability 10 4
retagging chunk 3, split with availability 46 22 10 4
retagging chunk 2, split with availability 190 46 22 10 4
retagging chunk 1, split with availability 382 190 46 22 10 4
retagging chunk 0, split with availability 766 382 190 46 22 10 4
successful
0: available sizes: 766 382 190 46 22 10 4
| 1: available sizes: 382 190 46 22 10 4
| | 2: available sizes: 190 46 22 10 4
| | | 3: available sizes: 46 22 10 4
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | 194: 190 words, FREE
| | 385: 382 words, FREE
| 768: 766 words, FREE
| 4: available sizes: 10 4
| | 5:46words,USEDbyaaa
| | 52:availablesizes:104
| | | 53:availablesizes:104
| | | | 54:availablesizes:4
| | | | | 55:4words,USEDbybbb | | | | |60:4words,FREE
| | | | 65:10words,FREE
| | | 76:22words,USEDbyccc
| 99:availablesizes:4622104
| | 100:availablesizes:22104
| | | 101:availablesizes:104
| | | | 102:availablesizes:4
| | | | | 103:4words,USEDbyfff | | | | |108:4words,FREE
| | | | 113:10words,FREE
| | | 124:22words,FREE
| | 147:46words,FREE
> free 76
requested deallocation of chunk 76
looking for chunk 76 in chunk 0, at level 8
split chuck, left 1 to 767, right 768 to 1534
looking for chunk 76 in chunk 1, at level 7
split chuck, left 2 to 384, right 385 to 767
looking for chunk 76 in chunk 2, at level 6
split chuck, left 3 to 193, right 194 to 384
looking for chunk 76 in chunk 3, at level 5
split chuck, left 4 to 98, right 99 to 193
looking for chunk 76 in chunk 4, at level 4
split chuck, left 5 to 51, right 52 to 98
looking for chunk 76 in chunk 52, at level 3
split chuck, left 53 to 75, right 76 to 98
looking for chunk 76 in chunk 76, at level 2
found it, marking as free, size 22
retagging chunk 52, split with availability 22 10 4
retagging chunk 4, split with availability 22 10 4
retagging chunk 3, split with availability 46 22 10 4
retagging chunk 2, split with availability 190 46 22 10 4
retagging chunk 1, split with availability 382 190 46 22 10 4
retagging chunk 0, split with availability 766 382 190 46 22 10 4
successful
0: available sizes: 766 382 190 46 22 10 4
| 1: available sizes: 382 190 46 22 10 4
| | 2: available sizes: 190 46 22 10 4
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| | 385: 382 words, FREE
| 768: 766 words, FREE
| 3: available sizes: 46 22 10 4
| | 4:availablesizes:22104
| | | 5:46words,USEDbyaaa
| | | 52:availablesizes:22104
| | | | 53:availablesizes:104
| | | | | 54:availablesizes:4
| | | | | | 55:4words,USEDbybbb | | | | | |60:4words,FREE
| | | | | 65:10words,FREE
| | | | 76:22words,FREE
| | 99:availablesizes:4622104
| | | 100:availablesizes:22104
| | | | 101:availablesizes:104
| | | | | 102:availablesizes:4
| | | | | | 103:4words,USEDbyfff | | | | | |108:4words,FREE
| | | | | 113:10words,FREE
| | | | 124:22words,FREE
| | | 147:46words,FREE
| 194: 190 words, FREE
> free 55
requested deallocation of chunk 55
looking for chunk 55 in chunk 0, at level 8
split chuck, left 1 to 767, right 768 to 1534
looking for chunk 55 in chunk 1, at level 7
split chuck, left 2 to 384, right 385 to 767
looking for chunk 55 in chunk 2, at level 6
split chuck, left 3 to 193, right 194 to 384
looking for chunk 55 in chunk 3, at level 5
split chuck, left 4 to 98, right 99 to 193
looking for chunk 55 in chunk 4, at level 4
split chuck, left 5 to 51, right 52 to 98
looking for chunk 55 in chunk 52, at level 3
split chuck, left 53 to 75, right 76 to 98
looking for chunk 55 in chunk 53, at level 2
split chuck, left 54 to 64, right 65 to 75
looking for chunk 55 in chunk 54, at level 1
split chuck, left 55 to 59, right 60 to 64
looking for chunk 55 in chunk 55, at level 0
found it, marking as free, size 4
recombining 55 and 60 to make 54 free
recombining 54 and 65 to make 53 free
recombining 53 and 76 to make 52 free
retagging chunk 4, split with availability 46
retagging chunk 3, split with availability 46 22 10 4
retagging chunk 2, split with availability 190 46 22 10 4
retagging chunk 1, split with availability 382 190 46 22 10 4
retagging chunk 0, split with availability 766 382 190 46 22 10 4
successful
0: available sizes: 766 382 190 46 22 10 4
| 1: available sizes: 382 190 46 22 10 4
| | 2: available sizes: 190 46 22 10 4
| | | 3: available sizes: 46 22 10 4
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | 194: 190 words, FREE
| | 385: 382 words, FREE
| 768: 766 words, FREE
| 4: available sizes: 46
| | 5:46words,USEDbyaaa
| | 52:46words,FREE
| 99:availablesizes:4622104
| | 100:availablesizes:22104
| | | 101:availablesizes:104
| | | | 102:availablesizes:4
| | | | | 103:4words,USEDbyfff | | | | |108:4words,FREE
| | | | 113:10words,FREE
| | | 124:22words,FREE
| | 147:46words,FREE
> free 103
requested deallocation of chunk 103
looking for chunk 103 in chunk 0, at level 8
split chuck, left 1 to 767, right 768 to 1534
looking for chunk 103 in chunk 1, at level 7
split chuck, left 2 to 384, right 385 to 767
looking for chunk 103 in chunk 2, at level 6
split chuck, left 3 to 193, right 194 to 384
looking for chunk 103 in chunk 3, at level 5
split chuck, left 4 to 98, right 99 to 193
looking for chunk 103 in chunk 99, at level 4
split chuck, left 100 to 146, right 147 to 193
looking for chunk 103 in chunk 100, at level 3
split chuck, left 101 to 123, right 124 to 146
looking for chunk 103 in chunk 101, at level 2
split chuck, left 102 to 112, right 113 to 123
looking for chunk 103 in chunk 102, at level 1
split chuck, left 103 to 107, right 108 to 112
looking for chunk 103 in chunk 103, at level 0
found it, marking as free, size 4
recombining 103 and 108 to make 102 free
recombining 102 and 113 to make 101 free
recombining 101 and 124 to make 100 free
recombining 100 and 147 to make 99 free
retagging chunk 3, split with availability 94 46
retagging chunk 2, split with availability 190 94 46
retagging chunk 1, split with availability 382 190 94 46
retagging chunk 0, split with availability 766 382 190 94 46
successful
0: available sizes: 766 382 190 94 46
| 1: available sizes: 382 190 94 46
| | 2: available sizes: 190 94 46
| | | 3: available sizes: 94 46
| | |
| | |
| | |
| | |
| | | 194: 190 words, FREE
| | 385: 382 words, FREE
| 4: available sizes: 46
| | 5:46words,USEDbyaaa | | 52:46words,FREE
| 99:94words,FREE
| 768: 766 words, FREE
> free 5
requested deallocation of chunk 5
looking for chunk 5 in chunk 0, at level 8
split chuck, left 1 to 767, right 768 to 1534
looking for chunk 5 in chunk 1, at level 7
split chuck, left 2 to 384, right 385 to 767
looking for chunk 5 in chunk 2, at level 6
split chuck, left 3 to 193, right 194 to 384
looking for chunk 5 in chunk 3, at level 5
split chuck, left 4 to 98, right 99 to 193
looking for chunk 5 in chunk 4, at level 4
split chuck, left 5 to 51, right 52 to 98
looking for chunk 5 in chunk 5, at level 3
found it, marking as free, size 46
recombining 5 and 52 to make 4 free
recombining 4 and 99 to make 3 free
recombining 3 and 194 to make 2 free
recombining 2 and 385 to make 1 free
recombining 1 and 768 to make 0 free
successful
0: 1534 words, FREE
> zzz 1000
requested allocation of 1000 words for ‘zzz’
will have to use a level 8 chunk of capacity 1534 words
at level 8, checking chunk starting at 0
a free chunk of the right size
successful
0: 1534 words, USED by zzz
> yyy 4
requested allocation of 4 words for ‘yyy’
will have to use a level 0 chunk of capacity 4 words
at level 8, checking chunk starting at 0
Impossible – this chunk is used (3)
failed
0: 1534 words, USED by zzz
> ^C