Rev 908 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
854 | serge | 1 | |
2 | #include |
||
3 | #include |
||
4 | #include |
||
5 | #include |
||
6 | |||
7 | |||
8 | |||
9 | |||
10 | |||
11 | |||
12 | |||
13 | |||
14 | |||
15 | |||
16 | |||
17 | static void __fastcall buddy_system_free(zone_t *z, link_t *block); |
||
18 | static void zone_mark_unavailable(zone_t *zone, index_t frame_idx); |
||
19 | |||
20 | |||
21 | void __fastcall zone_free(zone_t *zone, pfn_t frame_idx); |
||
859 | serge | 22 | |
854 | serge | 23 | |
24 | |||
25 | |||
26 | |||
27 | |||
28 | |||
29 | static void zone_reserve(zone_t *z, pfn_t base, count_t count); |
||
30 | static void zone_release(zone_t *z, pfn_t base, count_t count); |
||
31 | |||
32 | |||
33 | |||
34 | { |
||
35 | int i; |
||
36 | |||
37 | |||
38 | u32_t size; |
||
39 | count_t pages; |
||
40 | size_t conf_size; |
||
41 | size_t core_size; |
||
42 | |||
43 | |||
44 | DBG("last page = %x total pages = %x\n",mem_amount, pages); |
||
862 | serge | 45 | |
854 | serge | 46 | |
47 | DBG("conf_size = %x free mem start =%x\n",conf_size, pg_balloc); |
||
862 | serge | 48 | |
854 | serge | 49 | |
50 | |||
51 | |||
52 | zone_reserve(&z_core, 0, pg_balloc >> FRAME_WIDTH); |
||
53 | |||
54 | |||
55 | |||
56 | core_size = (pg_free+conf_size+1024*1024*5)&(-1024*1024*4); |
||
57 | // printf("core size = %x core heap = %x\n",core_size,core_size-conf_size-pg_free); |
||
58 | |||
59 | |||
60 | u32_t b0, b1; |
||
61 | |||
62 | |||
63 | p1 = (last_page-core_size)>>12; |
||
64 | |||
65 | |||
66 | b1 = p1*sizeof(frame_t); |
||
67 | |||
68 | |||
69 | // printf("buddy_1: %x pages conf_size %x\n", p1, b1); |
||
70 | |||
71 | |||
72 | zone_create(&z_user, p0, p1); |
||
73 | |||
74 | |||
75 | |||
76 | |||
77 | { |
||
78 | u32_t page; |
||
79 | if( mem_table[i].type != 1) |
||
80 | continue; |
||
81 | page = (mem_table[i].base+mem_table[i].size)&(~4095); |
||
82 | if(page > last_page) |
||
83 | last_page = page; |
||
84 | |||
85 | |||
86 | zone_release(&z_user,mem_table[i].base>>12, mem_table[i].size>>12); |
||
87 | }; |
||
88 | zone_reserve(&z_core, 0x100000>>12,(pg_balloc-OS_BASE-0x100000)>>12); |
||
89 | #endif |
||
90 | }; |
||
91 | |||
92 | |||
93 | { |
||
94 | unsigned int i; |
||
95 | // int znum; |
||
96 | |||
97 | |||
98 | * nobody tries to do that. If some platform requires, remove |
||
99 | * the assert |
||
100 | */ |
||
101 | // ASSERT(confframe); |
||
102 | /* If conframe is supposed to be inside our zone, then make sure |
||
103 | * it does not span kernel & init |
||
104 | */ |
||
105 | |||
106 | |||
107 | |||
108 | |||
109 | z->base = start; |
||
110 | z->count = count; |
||
111 | z->free_count = count; |
||
112 | z->busy_count = 0; |
||
113 | |||
114 | |||
115 | |||
116 | |||
117 | |||
118 | |||
119 | list_initialize(&z->order[i]); |
||
120 | |||
121 | |||
122 | |||
123 | |||
124 | frame_initialize(&z->frames[i]); |
||
125 | } |
||
126 | } |
||
127 | |||
128 | |||
129 | { |
||
130 | int i; |
||
131 | pfn_t top = base+count; |
||
132 | |||
133 | |||
134 | return; |
||
135 | |||
136 | |||
137 | base = z->base; |
||
138 | |||
139 | |||
140 | top = z->base+z->count; |
||
141 | |||
142 | |||
862 | serge | 143 | |
854 | serge | 144 | |
145 | zone_mark_unavailable(z, i - z->base); |
||
146 | |||
147 | |||
148 | |||
149 | |||
150 | { |
||
151 | int i; |
||
889 | serge | 152 | pfn_t top = base+count; |
153 | |||
854 | serge | 154 | |
889 | serge | 155 | return; |
156 | |||
854 | serge | 157 | |
889 | serge | 158 | base = z->base; |
159 | |||
854 | serge | 160 | |
889 | serge | 161 | top = z->base+z->count; |
162 | |||
854 | serge | 163 | |
889 | serge | 164 | |
854 | serge | 165 | |
889 | serge | 166 | z->frames[i-z->base].refcount = 0; |
167 | buddy_system_free(z, &z->frames[i-z->base].buddy_link); |
||
168 | } |
||
854 | serge | 169 | }; |
170 | |||
171 | |||
172 | |||
173 | { |
||
174 | return (index_t) (frame - zone->frames); |
||
175 | } |
||
176 | |||
177 | |||
178 | { |
||
179 | return (index_t) (frame - zone->frames); |
||
180 | } |
||
181 | |||
182 | |||
183 | { |
||
184 | return (index < zone->count); |
||
185 | } |
||
186 | |||
187 | |||
188 | static inline index_t make_frame_index(zone_t *zone, frame_t *frame) |
||
189 | { |
||
190 | return (frame - zone->frames); |
||
191 | } |
||
192 | |||
193 | |||
194 | { |
||
195 | frame->refcount = 1; |
||
196 | frame->buddy_order = 0; |
||
197 | } |
||
198 | |||
199 | |||
200 | |||
201 | u32_t order) |
||
202 | { |
||
203 | frame_t *frame; |
||
204 | index_t index; |
||
205 | |||
206 | |||
207 | |||
208 | |||
209 | do { |
||
210 | if (zone->frames[index].buddy_order != order) { |
||
211 | return &zone->frames[index].buddy_link; |
||
212 | } |
||
213 | } while(index-- > 0); |
||
214 | return NULL; |
||
215 | } |
||
216 | |||
217 | |||
218 | frame_t *frame_l, *frame_r; |
||
219 | |||
220 | |||
221 | frame_r = (frame_l + (1 << (frame_l->buddy_order - 1))); |
||
222 | |||
223 | |||
224 | } |
||
225 | |||
226 | |||
227 | frame_t *frame = (frame_t*)block; |
||
228 | return frame->buddy_order; |
||
229 | } |
||
230 | |||
231 | |||
232 | u32_t order) { |
||
233 | frame_t *frame = (frame_t*)block; |
||
234 | frame->buddy_order = order; |
||
235 | } |
||
236 | |||
237 | |||
238 | link_t *block_2) |
||
239 | { |
||
240 | frame_t *frame1, *frame2; |
||
241 | |||
242 | |||
243 | frame2 = (frame_t*)block_2; |
||
244 | |||
245 | |||
246 | } |
||
247 | |||
248 | |||
249 | frame_t * frame = (frame_t*)block; |
||
889 | serge | 250 | frame->refcount = 1; |
854 | serge | 251 | } |
252 | |||
253 | |||
254 | frame_t *frame = (frame_t*)block; |
||
889 | serge | 255 | frame->refcount = 0; |
854 | serge | 256 | } |
257 | |||
258 | |||
259 | ((~(((u32_t) -1) << (order)) & (index)) == 0) |
||
260 | #define IS_BUDDY_LEFT_BLOCK_ABS(zone, frame) \ |
||
261 | (((frame_index_abs((zone), (frame)) >> (frame)->buddy_order) & 0x1) == 0) |
||
262 | |||
263 | |||
264 | (((frame_index_abs((zone), (frame)) >> (frame)->buddy_order) & 0x1) == 1) |
||
265 | |||
266 | |||
267 | { |
||
268 | frame_t *frame; |
||
269 | index_t index; |
||
270 | u32_t is_left, is_right; |
||
889 | serge | 271 | |
854 | serge | 272 | |
889 | serge | 273 | ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame),frame->buddy_order)); |
274 | |||
854 | serge | 275 | |
276 | is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame); |
||
277 | |||
278 | |||
889 | serge | 279 | if (is_left) { |
854 | serge | 280 | index = (frame_index(zone, frame)) + (1 << frame->buddy_order); |
281 | } else { /* if (is_right) */ |
||
282 | index = (frame_index(zone, frame)) - (1 << frame->buddy_order); |
||
283 | } |
||
284 | |||
285 | |||
286 | if (zone->frames[index].buddy_order == frame->buddy_order && |
||
287 | zone->frames[index].refcount == 0) { |
||
288 | return &zone->frames[index].buddy_link; |
||
289 | } |
||
290 | } |
||
291 | |||
292 | |||
293 | } |
||
294 | |||
295 | |||
296 | { |
||
297 | link_t *left,*right, *tmp; |
||
298 | u32_t order; |
||
889 | serge | 299 | |
854 | serge | 300 | |
889 | serge | 301 | ASSERT(left); |
302 | list_remove(left); |
||
854 | serge | 303 | while (1) { |
304 | if (! buddy_get_order(z,left)) { |
||
889 | serge | 305 | buddy_mark_busy(z, left); |
306 | return left; |
||
854 | serge | 307 | } |
308 | |||
309 | |||
889 | serge | 310 | |
854 | serge | 311 | |
889 | serge | 312 | buddy_set_order(z, left, order-1); |
313 | buddy_set_order(z, right, order-1); |
||
314 | |||
854 | serge | 315 | |
889 | serge | 316 | |
854 | serge | 317 | |
889 | serge | 318 | right = left; |
319 | left = tmp; |
||
320 | } |
||
321 | ASSERT(tmp == left); |
||
322 | buddy_mark_busy(z, left); |
||
323 | buddy_system_free(z, right); |
||
324 | buddy_mark_available(z, left); |
||
325 | } |
||
854 | serge | 326 | } |
327 | |||
328 | |||
329 | { |
||
330 | link_t *buddy, *hlp; |
||
889 | serge | 331 | u8_t i; |
332 | |||
854 | serge | 333 | |
889 | serge | 334 | * Determine block's order. |
854 | serge | 335 | */ |
336 | i = buddy_get_order(z, block); |
||
889 | serge | 337 | |
854 | serge | 338 | |
889 | serge | 339 | |
854 | serge | 340 | |
889 | serge | 341 | /* |
854 | serge | 342 | * See if there is any buddy in the list of order i. |
343 | */ |
||
344 | buddy = find_buddy(z, block); |
||
889 | serge | 345 | if (buddy) { |
854 | serge | 346 | |
347 | |||
889 | serge | 348 | /* |
854 | serge | 349 | * Remove buddy from the list of order i. |
350 | */ |
||
351 | list_remove(buddy); |
||
352 | |||
353 | |||
354 | * Invalidate order of both block and buddy. |
||
355 | */ |
||
356 | buddy_set_order(z, block, BUDDY_SYSTEM_INNER_BLOCK); |
||
889 | serge | 357 | buddy_set_order(z, buddy, BUDDY_SYSTEM_INNER_BLOCK); |
358 | |||
854 | serge | 359 | |
360 | * Coalesce block and buddy into one block. |
||
361 | */ |
||
362 | hlp = buddy_coalesce(z, block, buddy); |
||
889 | serge | 363 | |
854 | serge | 364 | |
365 | * Set order of the coalesced block to i + 1. |
||
366 | */ |
||
367 | buddy_set_order(z, hlp, i + 1); |
||
889 | serge | 368 | |
854 | serge | 369 | |
370 | * Recursively add the coalesced block to the list of order i + 1. |
||
371 | */ |
||
372 | buddy_system_free(z, hlp); |
||
889 | serge | 373 | return; |
854 | serge | 374 | } |
375 | } |
||
376 | /* |
||
377 | * Insert block into the list of order i. |
||
378 | */ |
||
379 | list_append(block, &z->order[i]); |
||
889 | serge | 380 | } |
854 | serge | 381 | |
382 | |||
383 | { |
||
384 | ASSERT(frame_idx < zone->count); |
||
889 | serge | 385 | return &zone->frames[frame_idx]; |
854 | serge | 386 | } |
387 | |||
388 | |||
389 | { |
||
390 | frame_t *frame; |
||
391 | link_t *link; |
||
392 | |||
393 | |||
394 | if (frame->refcount) |
||
395 | return; |
||
396 | link = buddy_system_alloc_block(zone, &frame->buddy_link); |
||
889 | serge | 397 | ASSERT(link); |
398 | zone->free_count--; |
||
854 | serge | 399 | } |
400 | |||
401 | |||
402 | { |
||
403 | link_t *res, *hlp; |
||
404 | |||
405 | |||
889 | serge | 406 | |
854 | serge | 407 | |
408 | * If the list of order i is not empty, |
||
409 | * the request can be immediatelly satisfied. |
||
410 | */ |
||
411 | if (!list_empty(&z->order[i])) { |
||
412 | res = z->order[i].next; |
||
413 | list_remove(res); |
||
414 | buddy_mark_busy(z, res); |
||
415 | return res; |
||
416 | } |
||
417 | /* |
||
418 | * If order i is already the maximal order, |
||
419 | * the request cannot be satisfied. |
||
420 | */ |
||
421 | if (i == z->max_order) |
||
422 | return NULL; |
||
423 | |||
424 | |||
425 | * Try to recursively satisfy the request from higher order lists. |
||
426 | */ |
||
427 | hlp = buddy_system_alloc(z, i + 1); |
||
428 | |||
429 | |||
430 | * The request could not be satisfied |
||
431 | * from higher order lists. |
||
432 | */ |
||
433 | if (!hlp) |
||
434 | return NULL; |
||
435 | |||
436 | |||
437 | |||
438 | |||
439 | * Bisect the block and set order of both of its parts to i. |
||
440 | */ |
||
441 | hlp = buddy_bisect(z, res); |
||
442 | buddy_set_order(z, res, i); |
||
443 | buddy_set_order(z, hlp, i); |
||
444 | |||
445 | |||
446 | * Return the other half to buddy system. Mark the first part |
||
447 | * full, so that it won't coalesce again. |
||
448 | */ |
||
449 | buddy_mark_busy(z, res); |
||
450 | buddy_system_free(z, hlp); |
||
451 | |||
452 | |||
453 | |||
454 | |||
455 | |||
456 | |||
457 | |||
458 | { |
||
459 | pfn_t v; |
||
460 | link_t *tmp; |
||
461 | frame_t *frame; |
||
462 | |||
463 | |||
464 | |||
465 | tmp = buddy_system_alloc(zone, order); |
||
466 | |||
467 | |||
889 | serge | 468 | |
854 | serge | 469 | |
470 | zone->free_count -= (1 << order); |
||
471 | zone->busy_count += (1 << order); |
||
472 | |||
473 | |||
474 | frame = (frame_t*)tmp; |
||
475 | |||
476 | |||
477 | v = make_frame_index(zone, frame); |
||
478 | |||
859 | serge | 479 | |
854 | serge | 480 | } |
481 | |||
482 | |||
483 | |||
484 | void __fastcall frame_set_parent(pfn_t pfn, void *data) |
||
485 | { |
||
486 | /* zone_t *zone = find_zone_and_lock(pfn, &hint); |
||
487 | ASSERT(zone); |
||
488 | */ |
||
489 | |||
490 | |||
491 | zone_get_frame(&z_core, pfn-z_core.base)->parent = data; |
||
492 | spinlock_unlock(&z_core.lock); |
||
493 | } |
||
494 | |||
495 | |||
859 | serge | 496 | { |
497 | // zone_t *zone = find_zone_and_lock(pfn, &hint); |
||
498 | void *res; |
||
499 | |||
854 | serge | 500 | |
859 | serge | 501 | res = zone_get_frame(&z_core, pfn)->parent; |
502 | spinlock_unlock(&z_core.lock); |
||
503 | |||
504 | |||
505 | } |
||
506 | |||
507 | |||
854 | serge | 508 | { |
509 | int n; |
||
510 | asm volatile ( |
||
511 | "xorl %eax, %eax \n\t" |
||
886 | serge | 512 | "bsr %edx, %eax \n\t" |
513 | "incl %eax" |
||
514 | :"=a" (n) |
||
854 | serge | 515 | :"d"(arg) |
516 | ); |
||
517 | return n; |
||
518 | } |
||
519 | |||
520 | |||
521 | |||
522 | { |
||
523 | eflags_t efl; |
||
524 | pfn_t v; |
||
525 | |||
526 | |||
527 | spinlock_lock(&zone->lock); |
||
528 | v = zone_frame_alloc(zone, order); |
||
529 | v += zone->base; |
||
530 | spinlock_unlock(&zone->lock); |
||
531 | safe_sti(efl); |
||
532 | |||
533 | |||
534 | } |
||
535 | |||
536 | |||
888 | serge | 537 | { |
854 | serge | 538 | eflags_t efl; |
539 | pfn_t v; |
||
540 | |||
541 | |||
542 | spinlock_lock(&z_core.lock); |
||
543 | v = zone_frame_alloc(&z_core, order); |
||
544 | spinlock_unlock(&z_core.lock); |
||
545 | safe_sti(efl); |
||
546 | |||
888 | serge | 547 | |
1066 | serge | 548 | ((1< |
549 | |||
888 | serge | 550 | |
854 | serge | 551 | }; |
552 | |||
553 | |||
888 | serge | 554 | { |
854 | serge | 555 | eflags_t efl; |
556 | |||
859 | serge | 557 | |
1066 | serge | 558 | |
908 | serge | 559 | |
859 | serge | 560 | spinlock_lock(&z_core.lock); |
561 | // zone_free(&z_core, frame>>12); |
||
1066 | serge | 562 | spinlock_unlock(&z_core.lock); |
859 | serge | 563 | safe_sti(efl); |
564 | |||
888 | serge | 565 | |
908 | serge | 566 | |
888 | serge | 567 | |
859 | serge | 568 | |
569 | |||
570 | { |
||
571 | eflags_t efl; |
||
572 | u32_t edx; |
||
854 | serge | 573 | pfn_t v; |
574 | |||
575 | |||
576 | efl = safe_cli(); |
||
577 | spinlock_lock(&z_core.lock); |
||
578 | v = zone_frame_alloc(&z_core, 0); |
||
579 | spinlock_unlock(&z_core.lock); |
||
580 | safe_sti(efl); |
||
581 | |||
861 | serge | 582 | |
888 | serge | 583 | |
861 | serge | 584 | |
854 | serge | 585 | return (v << FRAME_WIDTH); |
586 | }; |
||
587 | |||
588 | |||
589 | { |
||
590 | frame_t *frame; |
||
591 | u32_t order; |
||
889 | serge | 592 | |
854 | serge | 593 | |
594 | |||
595 | |||
596 | order = frame->buddy_order; |
||
597 | |||
598 | |||
889 | serge | 599 | |
854 | serge | 600 | |
888 | serge | 601 | { |
602 | buddy_system_free(zone, &frame->buddy_link); |
||
854 | serge | 603 | |
604 | |||
605 | zone->free_count += (1 << order); |
||
606 | zone->busy_count -= (1 << order); |
||
607 | } |
||
608 | } |
||
609 | |||
610 | |||
611 | { |
||
612 | eflags_t efl; |
||
613 | zone_t *zone; |
||
614 | |||
615 | |||
616 | spinlock_lock(&z_core.lock); |
||
617 | zone_free(&z_core, frame>>12); |
||
618 | spinlock_unlock(&z_core.lock); |
||
619 | safe_sti(efl); |
||
620 | } |
||
621 | |||
622 | |||
859 | serge | 623 | { |
624 | return z_core.free_count; |
||
625 | }><>><>><>><>><> |
||
626 |