Rev 928 | Rev 1313 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
859 | serge | 1 | |
2 | #include |
||
3 | #include |
||
4 | #include |
||
5 | #include |
||
6 | |||
7 | |||
1066 | serge | 8 | |
888 | serge | 9 | |
1066 | serge | 10 | #define HF_SIZE (1 << HF_WIDTH) |
11 | |||
886 | serge | 12 | |
1066 | serge | 13 | |
859 | serge | 14 | |
1066 | serge | 15 | |
886 | serge | 16 | |
1066 | serge | 17 | |
888 | serge | 18 | |
859 | serge | 19 | |
1066 | serge | 20 | (index_t)( (frame) - z_heap.frames) |
21 | |||
886 | serge | 22 | |
1066 | serge | 23 | (index_t)( (frame) - z_heap.frames) |
24 | |||
859 | serge | 25 | |
26 | |||
1066 | serge | 27 | { |
28 | frame->refcount = 1; |
||
29 | frame->buddy_order = 0; |
||
30 | } |
||
31 | |||
886 | serge | 32 | |
1066 | serge | 33 | ((frame_t*)(block))->buddy_order |
34 | |||
886 | serge | 35 | |
36 | |||
1066 | serge | 37 | ((frame_t*)(block))->buddy_order = (order) |
38 | |||
859 | serge | 39 | |
1066 | serge | 40 | ((frame_t*)(block))->refcount = 1 |
41 | |||
859 | serge | 42 | |
43 | |||
1066 | serge | 44 | { |
45 | frame_t *frame_l, *frame_r; |
||
46 | |||
859 | serge | 47 | |
1066 | serge | 48 | frame_r = (frame_l + (1 << (frame_l->buddy_order - 1))); |
49 | |||
888 | serge | 50 | |
1066 | serge | 51 | } |
52 | |||
888 | serge | 53 | |
1066 | serge | 54 | { |
859 | serge | 55 | frame_t *frame1, *frame2; |
1066 | serge | 56 | |
859 | serge | 57 | |
1066 | serge | 58 | frame2 = (frame_t*)block_2; |
59 | |||
859 | serge | 60 | |
1066 | serge | 61 | } |
62 | |||
888 | serge | 63 | |
859 | serge | 64 | |
1066 | serge | 65 | (((heap_index_abs((frame)) >> (frame)->buddy_order) & 0x1) == 0) |
66 | |||
886 | serge | 67 | |
1066 | serge | 68 | (((heap_index_abs((frame)) >> (frame)->buddy_order) & 0x1) == 1) |
69 | |||
886 | serge | 70 | |
859 | serge | 71 | |
1066 | serge | 72 | { |
73 | frame_t *frame; |
||
74 | index_t index; |
||
75 | u32_t is_left, is_right; |
||
76 | |||
859 | serge | 77 | |
1066 | serge | 78 | // ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame),frame->buddy_order)); |
79 | |||
859 | serge | 80 | |
1066 | serge | 81 | is_right = IS_BUDDY_RIGHT_BLOCK_ABS( frame); |
82 | |||
859 | serge | 83 | |
1066 | serge | 84 | |
859 | serge | 85 | |
1066 | serge | 86 | index = (heap_index(frame)) + (1 << frame->buddy_order); |
87 | } |
||
88 | else { /* if (is_right) */ |
||
89 | index = (heap_index(frame)) - (1 << frame->buddy_order); |
||
90 | }; |
||
91 | |||
859 | serge | 92 | |
93 | |||
1066 | serge | 94 | { |
95 | if (z_heap.frames[index].buddy_order == frame->buddy_order && |
||
96 | z_heap.frames[index].refcount == 0) { |
||
97 | return &z_heap.frames[index].buddy_link; |
||
98 | } |
||
99 | } |
||
100 | |||
859 | serge | 101 | |
1066 | serge | 102 | } |
103 | |||
889 | serge | 104 | |
859 | serge | 105 | |
1066 | serge | 106 | { |
107 | link_t *buddy, *hlp; |
||
108 | u32_t i; |
||
109 | |||
862 | serge | 110 | |
1066 | serge | 111 | * Determine block's order. |
112 | */ |
||
113 | i = buddy_get_order(block); |
||
114 | |||
859 | serge | 115 | |
1066 | serge | 116 | |
886 | serge | 117 | |
1066 | serge | 118 | { |
889 | serge | 119 | /* |
1066 | serge | 120 | * See if there is any buddy in the list of order i. |
121 | */ |
||
122 | buddy = find_buddy( block ); |
||
123 | if (buddy) |
||
124 | { |
||
125 | |||
859 | serge | 126 | |
1066 | serge | 127 | /* |
128 | * Remove buddy from the list of order i. |
||
129 | */ |
||
130 | list_remove(buddy); |
||
131 | |||
859 | serge | 132 | |
1066 | serge | 133 | * Invalidate order of both block and buddy. |
134 | */ |
||
135 | buddy_set_order(block, BUDDY_SYSTEM_INNER_BLOCK); |
||
136 | buddy_set_order(buddy, BUDDY_SYSTEM_INNER_BLOCK); |
||
137 | |||
859 | serge | 138 | |
1066 | serge | 139 | * Coalesce block and buddy into one block. |
140 | */ |
||
141 | hlp = buddy_coalesce( block, buddy ); |
||
142 | |||
859 | serge | 143 | |
1066 | serge | 144 | * Set order of the coalesced block to i + 1. |
145 | */ |
||
146 | buddy_set_order(hlp, i + 1); |
||
147 | |||
859 | serge | 148 | |
1066 | serge | 149 | * Recursively add the coalesced block to the list of order i + 1. |
150 | */ |
||
151 | buddy_system_free( hlp ); |
||
152 | return; |
||
153 | } |
||
154 | } |
||
155 | /* |
||
156 | * Insert block into the list of order i. |
||
157 | */ |
||
158 | list_append(block, &z_heap.order[i]); |
||
159 | } |
||
160 | |||
859 | serge | 161 | |
886 | serge | 162 | |
1066 | serge | 163 | { |
859 | serge | 164 | link_t *res, *hlp; |
1066 | serge | 165 | |
859 | serge | 166 | |
1066 | serge | 167 | |
859 | serge | 168 | |
1066 | serge | 169 | * If the list of order i is not empty, |
170 | * the request can be immediatelly satisfied. |
||
171 | */ |
||
172 | if (!list_empty(&z_heap.order[i])) { |
||
173 | res = z_heap.order[i].next; |
||
174 | list_remove(res); |
||
175 | buddy_mark_busy(res); |
||
176 | return res; |
||
177 | } |
||
178 | /* |
||
179 | * If order i is already the maximal order, |
||
180 | * the request cannot be satisfied. |
||
181 | */ |
||
182 | if (i == z_heap.max_order) |
||
183 | return NULL; |
||
184 | |||
859 | serge | 185 | |
1066 | serge | 186 | * Try to recursively satisfy the request from higher order lists. |
187 | */ |
||
188 | hlp = buddy_system_alloc( i + 1 ); |
||
189 | |||
859 | serge | 190 | |
1066 | serge | 191 | * The request could not be satisfied |
192 | * from higher order lists. |
||
193 | */ |
||
194 | if (!hlp) |
||
195 | return NULL; |
||
196 | |||
859 | serge | 197 | |
1066 | serge | 198 | |
859 | serge | 199 | |
1066 | serge | 200 | * Bisect the block and set order of both of its parts to i. |
201 | */ |
||
202 | hlp = buddy_bisect( res ); |
||
203 | |||
861 | serge | 204 | |
1066 | serge | 205 | buddy_set_order(hlp, i); |
206 | |||
886 | serge | 207 | |
1066 | serge | 208 | * Return the other half to buddy system. Mark the first part |
209 | * full, so that it won't coalesce again. |
||
210 | */ |
||
211 | buddy_mark_busy(res); |
||
212 | buddy_system_free( hlp ); |
||
213 | |||
886 | serge | 214 | |
1066 | serge | 215 | } |
216 | |||
886 | serge | 217 | |
218 | |||
1066 | serge | 219 | { |
220 | count_t i; |
||
221 | count_t count; |
||
222 | |||
886 | serge | 223 | |
1066 | serge | 224 | |
886 | serge | 225 | |
1066 | serge | 226 | ASSERT( count != 0); |
227 | |||
886 | serge | 228 | |
1066 | serge | 229 | |
886 | serge | 230 | |
1066 | serge | 231 | z_heap.count = count; |
232 | z_heap.free_count = count; |
||
233 | z_heap.busy_count = 0; |
||
234 | |||
861 | serge | 235 | |
1066 | serge | 236 | |
888 | serge | 237 | |
1066 | serge | 238 | |
862 | serge | 239 | |
1066 | serge | 240 | |
862 | serge | 241 | |
1066 | serge | 242 | list_initialize(&z_heap.order[i]); |
243 | |||
862 | serge | 244 | |
859 | serge | 245 | |
1066 | serge | 246 | count, sizeof(frame_t), PAGE_SIZE); |
247 | |||
859 | serge | 248 | |
1066 | serge | 249 | |
859 | serge | 250 | |
251 | |||
1066 | serge | 252 | return 0; |
253 | |||
859 | serge | 254 | |
255 | |||
1066 | serge | 256 | z_heap.frames[i].buddy_order=0; |
257 | z_heap.frames[i].parent = NULL; |
||
258 | z_heap.frames[i].refcount=1; |
||
259 | } |
||
260 | |||
859 | serge | 261 | |
1066 | serge | 262 | { |
263 | z_heap.frames[i].refcount = 0; |
||
264 | buddy_system_free(&z_heap.frames[i].buddy_link); |
||
265 | } |
||
266 | |||
861 | serge | 267 | |
1066 | serge | 268 | |
861 | serge | 269 | |
1066 | serge | 270 | } |
859 | serge | 271 | |
272 | |||
1066 | serge | 273 | { |
886 | serge | 274 | eflags_t efl; |
1066 | serge | 275 | addr_t heap = 0; |
276 | |||
888 | serge | 277 | |
1066 | serge | 278 | frame_t *frame; |
279 | index_t v; |
||
280 | int i; |
||
281 | mmap_t *map; |
||
282 | count_t pages; |
||
283 | |||
888 | serge | 284 | |
1066 | serge | 285 | |
888 | serge | 286 | |
1066 | serge | 287 | |
888 | serge | 288 | |
1066 | serge | 289 | |
888 | serge | 290 | |
1066 | serge | 291 | // sizeof(addr_t) * pages); |
292 | |||
888 | serge | 293 | |
1066 | serge | 294 | sizeof(addr_t) * pages) >> PAGE_WIDTH)); |
295 | |||
888 | serge | 296 | |
1066 | serge | 297 | |
298 | |||
299 | { |
||
888 | serge | 300 | order = size >> HF_WIDTH; |
1066 | serge | 301 | |
888 | serge | 302 | |
1066 | serge | 303 | order = fnzb(order - 1) + 1; |
304 | |||
888 | serge | 305 | |
1066 | serge | 306 | |
888 | serge | 307 | |
1066 | serge | 308 | |
888 | serge | 309 | |
1066 | serge | 310 | |
888 | serge | 311 | |
1066 | serge | 312 | |
888 | serge | 313 | |
1066 | serge | 314 | { |
888 | serge | 315 | addr_t page = 0; |
1066 | serge | 316 | addr_t mem; |
317 | |||
888 | serge | 318 | |
1066 | serge | 319 | z_heap.busy_count += (1 << order); |
320 | |||
888 | serge | 321 | |
1066 | serge | 322 | |
888 | serge | 323 | |
1066 | serge | 324 | |
888 | serge | 325 | |
1066 | serge | 326 | |
888 | serge | 327 | |
1066 | serge | 328 | |
888 | serge | 329 | |
1066 | serge | 330 | frame[i].parent = map; |
331 | |||
888 | serge | 332 | |
1066 | serge | 333 | |
888 | serge | 334 | |
1066 | serge | 335 | |
888 | serge | 336 | |
337 | |||
1066 | serge | 338 | addr_t *mpte = &map->pte[0]; |
339 | |||
888 | serge | 340 | |
1066 | serge | 341 | if( flags & PG_MAP ) |
342 | page = PG_DEMAND | (flags & 0xFFF); |
||
343 | |||
888 | serge | 344 | |
1066 | serge | 345 | while(pages--) |
346 | { |
||
888 | serge | 347 | *pte++ = 0; //page; |
1066 | serge | 348 | *mpte++ = page; |
349 | |||
888 | serge | 350 | |
1066 | serge | 351 | mem+= 4096; |
352 | }; |
||
888 | serge | 353 | #else |
1066 | serge | 354 | mem = heap; |
355 | |||
888 | serge | 356 | |
1066 | serge | 357 | { |
358 | if( flags & PG_MAP ) |
||
359 | page = alloc_page(); |
||
360 | |||
888 | serge | 361 | |
1066 | serge | 362 | |
888 | serge | 363 | |
1066 | serge | 364 | *mpte++ = page; |
365 | |||
888 | serge | 366 | |
1066 | serge | 367 | mem+= 4096; |
368 | }; |
||
369 | #endif |
||
370 | |||
888 | serge | 371 | |
1066 | serge | 372 | |
888 | serge | 373 | |
1066 | serge | 374 | } |
375 | |||
886 | serge | 376 | |
1066 | serge | 377 | |
888 | serge | 378 | |
1066 | serge | 379 | |
886 | serge | 380 | |
1066 | serge | 381 | }; |
382 | |||
886 | serge | 383 | |
1066 | serge | 384 | } |
385 | |||
886 | serge | 386 | |
1066 | serge | 387 | { |
388 | eflags_t efl; |
||
389 | frame_t *frame; |
||
390 | count_t idx; |
||
391 | |||
886 | serge | 392 | |
1066 | serge | 393 | |
886 | serge | 394 | |
1066 | serge | 395 | (idx >= z_heap.base+z_heap.count)) { |
396 | DBG("invalid address %x\n", addr); |
||
397 | return; |
||
398 | } |
||
399 | |||
886 | serge | 400 | |
1066 | serge | 401 | |
886 | serge | 402 | |
1066 | serge | 403 | |
886 | serge | 404 | |
1066 | serge | 405 | |
886 | serge | 406 | |
1066 | serge | 407 | |
886 | serge | 408 | |
1066 | serge | 409 | |
886 | serge | 410 | |
1066 | serge | 411 | |
886 | serge | 412 | |
1066 | serge | 413 | { |
888 | serge | 414 | mmap_t *map; |
1066 | serge | 415 | count_t i; |
416 | |||
888 | serge | 417 | |
1066 | serge | 418 | |
859 | serge | 419 | |
1066 | serge | 420 | frame[i].parent = NULL; |
421 | |||
859 | serge | 422 | |
1066 | serge | 423 | |
859 | serge | 424 | |
1066 | serge | 425 | z_heap.free_count += (1 << order); |
426 | z_heap.busy_count -= (1 << order); |
||
427 | |||
888 | serge | 428 | |
1066 | serge | 429 | safe_sti(efl); |
430 | |||
859 | serge | 431 | |
1066 | serge | 432 | frame_free(map->pte[i]); |
433 | |||
859 | serge | 434 | |
1066 | serge | 435 | } |
436 | else |
||
888 | serge | 437 | { |
438 | spinlock_unlock(&z_heap.lock); |
||
1066 | serge | 439 | safe_sti(efl); |
440 | }; |
||
888 | serge | 441 | }; |
859 | serge | 442 | |
443 | |||
888 | serge | 444 | |
1066 | serge | 445 | { |
859 | serge | 446 | index_t idx; |
1066 | serge | 447 | frame_t *frame; |
448 | mmap_t *map; |
||
449 | |||
859 | serge | 450 | |
1066 | serge | 451 | |
859 | serge | 452 | |
1066 | serge | 453 | |
886 | serge | 454 | |
1066 | serge | 455 | |
886 | serge | 456 | |
1066 | serge | 457 | |
886 | serge | 458 | |
1066 | serge | 459 | { |
889 | serge | 460 | addr_t page; |
1066 | serge | 461 | |
886 | serge | 462 | |
1066 | serge | 463 | |
889 | serge | 464 | |
1066 | serge | 465 | |
889 | serge | 466 | |
1066 | serge | 467 | { |
892 | serge | 468 | #if 0 |
1066 | serge | 469 | if( page & PG_DEMAND) |
470 | { |
||
471 | page &= ~PG_DEMAND; |
||
472 | page = alloc_page() | (page & 0xFFF); |
||
473 | |||
892 | serge | 474 | |
1066 | serge | 475 | }; |
892 | serge | 476 | #endif |
1066 | serge | 477 | ((addr_t*)page_tabs)[faddr >> PAGE_WIDTH] = page; |
478 | }; |
||
479 | }; |
||
889 | serge | 480 | }; |
859 | serge | 481 | |
482 | |||
1066 | serge | 483 |