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