Rev 701 | Rev 788 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 701 | Rev 735 | ||
---|---|---|---|
Line 66... | Line 66... | ||
66 | 66 | ||
67 | if (b) { |
67 | if (b) { |
68 | /* |
68 | /* |
69 | * Allocate memory for all orders this buddy system will work with. |
69 | * Allocate memory for all orders this buddy system will work with. |
70 | */ |
70 | */ |
71 | b->order = (link_t *) early_malloc(max_order * sizeof(link_t)); |
71 | b->order = (link_t *) early_malloc((max_order + 1) * sizeof(link_t)); |
72 | if (!b->order) { |
72 | if (!b->order) { |
73 | early_free(b); |
73 | early_free(b); |
74 | return NULL; |
74 | return NULL; |
75 | } |
75 | } |
76 | 76 | ||
77 | for (i = 0; i < max_order; i++) |
77 | for (i = 0; i <= max_order; i++) |
78 | list_initialize(&b->order[i]); |
78 | list_initialize(&b->order[i]); |
79 | 79 | ||
80 | b->max_order = max_order; |
80 | b->max_order = max_order; |
81 | b->op = op; |
81 | b->op = op; |
82 | b->data = data; |
82 | b->data = data; |
Line 93... | Line 93... | ||
93 | * @return True if block can be allocated |
93 | * @return True if block can be allocated |
94 | */ |
94 | */ |
95 | bool buddy_system_can_alloc(buddy_system_t *b, __u8 i) { |
95 | bool buddy_system_can_alloc(buddy_system_t *b, __u8 i) { |
96 | __u8 k; |
96 | __u8 k; |
97 | 97 | ||
- | 98 | /* |
|
- | 99 | * If requested block is greater then maximal block |
|
- | 100 | * we know immediatly that we cannot satisfy the request. |
|
- | 101 | */ |
|
98 | ASSERT(i < b->max_order); |
102 | if (i > b->max_order) return false; |
99 | 103 | ||
- | 104 | /* |
|
- | 105 | * Check if any bigger or equal order has free elements |
|
- | 106 | */ |
|
100 | for (k=i; k < b->max_order; k++) { |
107 | for (k=i; k <= b->max_order; k++) { |
101 | if (!list_empty(&b->order[k])) { |
108 | if (!list_empty(&b->order[k])) { |
102 | return true; |
109 | return true; |
103 | } |
110 | } |
104 | } |
111 | } |
105 | 112 | ||
Line 116... | Line 123... | ||
116 | */ |
123 | */ |
117 | link_t *buddy_system_alloc(buddy_system_t *b, __u8 i) |
124 | link_t *buddy_system_alloc(buddy_system_t *b, __u8 i) |
118 | { |
125 | { |
119 | link_t *res, *hlp; |
126 | link_t *res, *hlp; |
120 | 127 | ||
121 | ASSERT(i < b->max_order); |
128 | ASSERT(i <= b->max_order); |
122 | 129 | ||
123 | /* |
130 | /* |
124 | * If the list of order i is not empty, |
131 | * If the list of order i is not empty, |
125 | * the request can be immediatelly satisfied. |
132 | * the request can be immediatelly satisfied. |
126 | */ |
133 | */ |
Line 133... | Line 140... | ||
133 | 140 | ||
134 | /* |
141 | /* |
135 | * If order i is already the maximal order, |
142 | * If order i is already the maximal order, |
136 | * the request cannot be satisfied. |
143 | * the request cannot be satisfied. |
137 | */ |
144 | */ |
138 | if (i == b->max_order - 1) |
145 | if (i == b->max_order) |
139 | return NULL; |
146 | return NULL; |
140 | 147 | ||
141 | /* |
148 | /* |
142 | * Try to recursively satisfy the request from higher order lists. |
149 | * Try to recursively satisfy the request from higher order lists. |
143 | */ |
150 | */ |
Line 183... | Line 190... | ||
183 | /* |
190 | /* |
184 | * Determine block's order. |
191 | * Determine block's order. |
185 | */ |
192 | */ |
186 | i = b->op->get_order(b, block); |
193 | i = b->op->get_order(b, block); |
187 | 194 | ||
188 | ASSERT(i < b->max_order); |
195 | ASSERT(i <= b->max_order); |
189 | 196 | ||
190 | if (i != b->max_order - 1) { |
197 | if (i != b->max_order) { |
191 | /* |
198 | /* |
192 | * See if there is any buddy in the list of order i. |
199 | * See if there is any buddy in the list of order i. |
193 | */ |
200 | */ |
194 | buddy = b->op->find_buddy(b, block); |
201 | buddy = b->op->find_buddy(b, block); |
195 | if (buddy) { |
202 | if (buddy) { |
Line 243... | Line 250... | ||
243 | 250 | ||
244 | 251 | ||
245 | printf("Order\tBlocks\tSize \tBlock size\tElems per block\n"); |
252 | printf("Order\tBlocks\tSize \tBlock size\tElems per block\n"); |
246 | printf("-----\t------\t--------\t----------\t---------------\n"); |
253 | printf("-----\t------\t--------\t----------\t---------------\n"); |
247 | 254 | ||
248 | for (i=0;i < b->max_order; i++) { |
255 | for (i=0;i <= b->max_order; i++) { |
249 | cnt = 0; |
256 | cnt = 0; |
250 | if (!list_empty(&b->order[i])) { |
257 | if (!list_empty(&b->order[i])) { |
251 | for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next) |
258 | for (cur = b->order[i].next; cur != &b->order[i]; cur = cur->next) |
252 | cnt++; |
259 | cnt++; |
253 | } |
260 | } |