Rev 1387 | Rev 1409 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1387 | Rev 1403 | ||
---|---|---|---|
Line 90... | Line 90... | ||
90 | 90 | ||
91 | static int area_flags_to_page_flags(int aflags); |
91 | static int area_flags_to_page_flags(int aflags); |
92 | static int get_area_flags(as_area_t *a); |
92 | static int get_area_flags(as_area_t *a); |
93 | static as_area_t *find_area_and_lock(as_t *as, __address va); |
93 | static as_area_t *find_area_and_lock(as_t *as, __address va); |
94 | static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area); |
94 | static bool check_area_conflicts(as_t *as, __address va, size_t size, as_area_t *avoid_area); |
95 | int used_space_insert(as_area_t *a, __address page, count_t count); |
95 | static int used_space_insert(as_area_t *a, __address page, count_t count); |
96 | int used_space_remove(as_area_t *a, __address page, count_t count); |
96 | static int used_space_remove(as_area_t *a, __address page, count_t count); |
97 | 97 | ||
98 | /** Initialize address space subsystem. */ |
98 | /** Initialize address space subsystem. */ |
99 | void as_init(void) |
99 | void as_init(void) |
100 | { |
100 | { |
101 | as_arch_init(); |
101 | as_arch_init(); |
Line 242... | Line 242... | ||
242 | interrupts_restore(ipl); |
242 | interrupts_restore(ipl); |
243 | return EPERM; |
243 | return EPERM; |
244 | } |
244 | } |
245 | 245 | ||
246 | if (pages < area->pages) { |
246 | if (pages < area->pages) { |
247 | int i; |
247 | bool cond; |
- | 248 | __address start_free = area->base + pages*PAGE_SIZE; |
|
248 | 249 | ||
249 | /* |
250 | /* |
250 | * Shrinking the area. |
251 | * Shrinking the area. |
251 | * No need to check for overlaps. |
252 | * No need to check for overlaps. |
252 | */ |
253 | */ |
253 | for (i = pages; i < area->pages; i++) { |
- | |
254 | pte_t *pte; |
- | |
255 | 254 | ||
256 | /* |
255 | /* |
257 | * Releasing physical memory. |
256 | * Remove frames belonging to used space starting from |
- | 257 | * the highest addresses downwards until an overlap with |
|
- | 258 | * the resized address space area is found. Note that this |
|
258 | * This depends on the fact that the memory was allocated using frame_alloc(). |
259 | * is also the right way to remove part of the used_space |
- | 260 | * B+tree leaf list. |
|
259 | */ |
261 | */ |
260 | page_table_lock(as, false); |
- | |
261 | pte = page_mapping_find(as, area->base + i*PAGE_SIZE); |
- | |
262 | if (pte && PTE_VALID(pte)) { |
262 | for (cond = true; cond;) { |
263 | __address frame; |
263 | btree_node_t *node; |
264 | 264 | ||
265 | ASSERT(PTE_PRESENT(pte)); |
265 | ASSERT(!list_empty(&area->used_space.leaf_head)); |
- | 266 | node = list_get_instance(area->used_space.leaf_head.prev, btree_node_t, leaf_link); |
|
266 | frame = PTE_GET_FRAME(pte); |
267 | if ((cond = (bool) node->keys)) { |
- | 268 | __address b = node->key[node->keys - 1]; |
|
- | 269 | count_t c = (count_t) node->value[node->keys - 1]; |
|
- | 270 | int i = 0; |
|
- | 271 | ||
267 | page_mapping_remove(as, area->base + i*PAGE_SIZE); |
272 | if (overlaps(b, c*PAGE_SIZE, area->base, pages*PAGE_SIZE)) { |
- | 273 | ||
- | 274 | if (b + c*PAGE_SIZE <= start_free) { |
|
- | 275 | /* |
|
268 | page_table_unlock(as, false); |
276 | * The whole interval fits completely |
- | 277 | * in the resized address space area. |
|
- | 278 | */ |
|
- | 279 | break; |
|
- | 280 | } |
|
- | 281 | ||
- | 282 | /* |
|
- | 283 | * Part of the interval corresponding to b and c |
|
- | 284 | * overlaps with the resized address space area. |
|
- | 285 | */ |
|
269 | 286 | ||
- | 287 | cond = false; /* we are almost done */ |
|
270 | frame_free(ADDR2PFN(frame)); |
288 | i = (start_free - b) >> PAGE_WIDTH; |
- | 289 | if (!used_space_remove(area, start_free, c - i)) |
|
- | 290 | panic("Could not remove used space."); |
|
271 | } else { |
291 | } else { |
- | 292 | /* |
|
- | 293 | * The interval of used space can be completely removed. |
|
- | 294 | */ |
|
- | 295 | if (!used_space_remove(area, b, c)) |
|
- | 296 | panic("Could not remove used space.\n"); |
|
- | 297 | } |
|
- | 298 | ||
- | 299 | for (; i < c; i++) { |
|
- | 300 | pte_t *pte; |
|
- | 301 | ||
- | 302 | page_table_lock(as, false); |
|
- | 303 | pte = page_mapping_find(as, b + i*PAGE_SIZE); |
|
- | 304 | ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte)); |
|
- | 305 | frame_free(ADDR2PFN(PTE_GET_FRAME(pte))); |
|
- | 306 | page_mapping_remove(as, b + i*PAGE_SIZE); |
|
272 | page_table_unlock(as, false); |
307 | page_table_unlock(as, false); |
273 | } |
308 | } |
274 | } |
309 | } |
- | 310 | } |
|
275 | /* |
311 | /* |
276 | * Invalidate TLB's. |
312 | * Invalidate TLB's. |
277 | */ |
313 | */ |
278 | tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages); |
314 | tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages); |
279 | tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages); |
315 | tlb_invalidate_pages(AS->asid, area->base + pages*PAGE_SIZE, area->pages - pages); |
Line 310... | Line 346... | ||
310 | int as_area_destroy(as_t *as, __address address) |
346 | int as_area_destroy(as_t *as, __address address) |
311 | { |
347 | { |
312 | as_area_t *area; |
348 | as_area_t *area; |
313 | __address base; |
349 | __address base; |
314 | ipl_t ipl; |
350 | ipl_t ipl; |
315 | int i; |
- | |
316 | 351 | ||
317 | ipl = interrupts_disable(); |
352 | ipl = interrupts_disable(); |
318 | mutex_lock(&as->lock); |
353 | mutex_lock(&as->lock); |
319 | 354 | ||
320 | area = find_area_and_lock(as, address); |
355 | area = find_area_and_lock(as, address); |
Line 323... | Line 358... | ||
323 | interrupts_restore(ipl); |
358 | interrupts_restore(ipl); |
324 | return ENOENT; |
359 | return ENOENT; |
325 | } |
360 | } |
326 | 361 | ||
327 | base = area->base; |
362 | base = area->base; |
328 | for (i = 0; i < area->pages; i++) { |
363 | if (!(area->flags & AS_AREA_DEVICE)) { |
329 | pte_t *pte; |
364 | bool cond; |
330 | 365 | ||
331 | /* |
366 | /* |
332 | * Releasing physical memory. |
367 | * Releasing physical memory. |
333 | * Areas mapping memory-mapped devices are treated differently than |
368 | * Areas mapping memory-mapped devices are treated differently than |
334 | * areas backing frame_alloc()'ed memory. |
369 | * areas backing frame_alloc()'ed memory. |
335 | */ |
370 | */ |
- | 371 | ||
- | 372 | /* |
|
- | 373 | * Visit only the pages mapped by used_space B+tree. |
|
- | 374 | * Note that we must be very careful when walking the tree |
|
- | 375 | * leaf list and removing used space as the leaf list changes |
|
- | 376 | * unpredictibly after each remove. The solution is to actually |
|
- | 377 | * not walk the tree at all, but to remove items from the head |
|
- | 378 | * of the leaf list until there are some keys left. |
|
- | 379 | */ |
|
- | 380 | for (cond = true; cond;) { |
|
- | 381 | btree_node_t *node; |
|
- | 382 | ||
- | 383 | ASSERT(!list_empty(&area->used_space.leaf_head)); |
|
- | 384 | node = list_get_instance(area->used_space.leaf_head.next, btree_node_t, leaf_link); |
|
- | 385 | if ((cond = (bool) node->keys)) { |
|
- | 386 | __address b = node->key[0]; |
|
- | 387 | count_t i; |
|
- | 388 | pte_t *pte; |
|
- | 389 | ||
- | 390 | for (i = 0; i < (count_t) node->value[0]; i++) { |
|
336 | page_table_lock(as, false); |
391 | page_table_lock(as, false); |
337 | pte = page_mapping_find(as, area->base + i*PAGE_SIZE); |
392 | pte = page_mapping_find(as, b + i*PAGE_SIZE); |
338 | if (pte && PTE_VALID(pte)) { |
393 | ASSERT(pte && PTE_VALID(pte) && PTE_PRESENT(pte)); |
339 | ASSERT(PTE_PRESENT(pte)); |
394 | frame_free(ADDR2PFN(PTE_GET_FRAME(pte))); |
340 | page_mapping_remove(as, area->base + i*PAGE_SIZE); |
395 | page_mapping_remove(as, b + i*PAGE_SIZE); |
341 | if (area->flags & AS_AREA_DEVICE) { |
- | |
342 | __address frame; |
- | |
343 | frame = PTE_GET_FRAME(pte); |
- | |
344 | frame_free(ADDR2PFN(frame)); |
- | |
345 | } |
- | |
346 | page_table_unlock(as, false); |
- | |
347 | } else { |
- | |
348 | page_table_unlock(as, false); |
396 | page_table_unlock(as, false); |
349 | } |
397 | } |
- | 398 | if (!used_space_remove(area, b, i)) |
|
- | 399 | panic("Could not remove used space.\n"); |
|
- | 400 | } |
|
- | 401 | } |
|
350 | } |
402 | } |
- | 403 | btree_destroy(&area->used_space); |
|
- | 404 | ||
351 | /* |
405 | /* |
352 | * Invalidate TLB's. |
406 | * Invalidate TLB's. |
353 | */ |
407 | */ |
354 | tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base, area->pages); |
408 | tlb_shootdown_start(TLB_INVL_PAGES, AS->asid, area->base, area->pages); |
355 | tlb_invalidate_pages(AS->asid, area->base, area->pages); |
409 | tlb_invalidate_pages(AS->asid, area->base, area->pages); |
Line 417... | Line 471... | ||
417 | src_size = src_area->pages * PAGE_SIZE; |
471 | src_size = src_area->pages * PAGE_SIZE; |
418 | src_flags = src_area->flags; |
472 | src_flags = src_area->flags; |
419 | mutex_unlock(&src_area->lock); |
473 | mutex_unlock(&src_area->lock); |
420 | mutex_unlock(&src_as->lock); |
474 | mutex_unlock(&src_as->lock); |
421 | 475 | ||
422 | - | ||
423 | if (src_size != acc_size) { |
476 | if (src_size != acc_size) { |
424 | spinlock_unlock(&src_task->lock); |
477 | spinlock_unlock(&src_task->lock); |
425 | interrupts_restore(ipl); |
478 | interrupts_restore(ipl); |
426 | return EPERM; |
479 | return EPERM; |
427 | } |
480 | } |
Line 510... | Line 563... | ||
510 | ipl = interrupts_disable(); |
563 | ipl = interrupts_disable(); |
511 | page_table_lock(as, true); |
564 | page_table_lock(as, true); |
512 | 565 | ||
513 | area = find_area_and_lock(as, page); |
566 | area = find_area_and_lock(as, page); |
514 | if (!area) { |
567 | if (!area) { |
515 | panic("page not part of any as_area\n"); |
568 | panic("Page not part of any as_area.\n"); |
516 | } |
569 | } |
517 | 570 | ||
518 | page_mapping_insert(as, page, frame, get_area_flags(area)); |
571 | page_mapping_insert(as, page, frame, get_area_flags(area)); |
- | 572 | if (!used_space_insert(area, page, 1)) |
|
- | 573 | panic("Could not insert used space.\n"); |
|
519 | 574 | ||
520 | mutex_unlock(&area->lock); |
575 | mutex_unlock(&area->lock); |
521 | page_table_unlock(as, true); |
576 | page_table_unlock(as, true); |
522 | interrupts_restore(ipl); |
577 | interrupts_restore(ipl); |
523 | } |
578 | } |
Line 603... | Line 658... | ||
603 | * Map 'page' to 'frame'. |
658 | * Map 'page' to 'frame'. |
604 | * Note that TLB shootdown is not attempted as only new information is being |
659 | * Note that TLB shootdown is not attempted as only new information is being |
605 | * inserted into page tables. |
660 | * inserted into page tables. |
606 | */ |
661 | */ |
607 | page_mapping_insert(AS, page, frame, get_area_flags(area)); |
662 | page_mapping_insert(AS, page, frame, get_area_flags(area)); |
- | 663 | if (!used_space_insert(area, ALIGN_DOWN(page, PAGE_SIZE), 1)) |
|
- | 664 | panic("Could not insert used space.\n"); |
|
608 | page_table_unlock(AS, false); |
665 | page_table_unlock(AS, false); |
609 | 666 | ||
610 | mutex_unlock(&area->lock); |
667 | mutex_unlock(&area->lock); |
611 | mutex_unlock(&AS->lock); |
668 | mutex_unlock(&AS->lock); |
612 | return AS_PF_OK; |
669 | return AS_PF_OK; |
Line 994... | Line 1051... | ||
994 | } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) { |
1051 | } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) { |
995 | /* The interval intersects with the right interval. */ |
1052 | /* The interval intersects with the right interval. */ |
996 | return 0; |
1053 | return 0; |
997 | } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
1054 | } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
998 | /* The interval can be added by merging the two already present intervals. */ |
1055 | /* The interval can be added by merging the two already present intervals. */ |
999 | node->value[node->keys - 1] += (count_t) count + right_cnt; |
1056 | node->value[node->keys - 1] += count + right_cnt; |
1000 | btree_remove(&a->used_space, right_pg, leaf); |
1057 | btree_remove(&a->used_space, right_pg, leaf); |
1001 | return 1; |
1058 | return 1; |
1002 | } else if (page == left_pg + left_cnt*PAGE_SIZE) { |
1059 | } else if (page == left_pg + left_cnt*PAGE_SIZE) { |
1003 | /* The interval can be added by simply growing the left interval. */ |
1060 | /* The interval can be added by simply growing the left interval. */ |
1004 | node->value[node->keys - 1] += (count_t) count; |
1061 | node->value[node->keys - 1] += count; |
1005 | return 1; |
1062 | return 1; |
1006 | } else if (page + count*PAGE_SIZE == right_pg) { |
1063 | } else if (page + count*PAGE_SIZE == right_pg) { |
1007 | /* |
1064 | /* |
1008 | * The interval can be addded by simply moving base of the right |
1065 | * The interval can be addded by simply moving base of the right |
1009 | * interval down and increasing its size accordingly. |
1066 | * interval down and increasing its size accordingly. |
1010 | */ |
1067 | */ |
1011 | leaf->value[0] += (count_t) count; |
1068 | leaf->value[0] += count; |
1012 | leaf->key[0] = page; |
1069 | leaf->key[0] = page; |
1013 | return 1; |
1070 | return 1; |
1014 | } else { |
1071 | } else { |
1015 | /* |
1072 | /* |
1016 | * The interval is between both neigbouring intervals, |
1073 | * The interval is between both neigbouring intervals, |
Line 1035... | Line 1092... | ||
1035 | /* |
1092 | /* |
1036 | * The interval can be added by moving the base of the right interval down |
1093 | * The interval can be added by moving the base of the right interval down |
1037 | * and increasing its size accordingly. |
1094 | * and increasing its size accordingly. |
1038 | */ |
1095 | */ |
1039 | leaf->key[0] = page; |
1096 | leaf->key[0] = page; |
1040 | leaf->value[0] += (count_t) count; |
1097 | leaf->value[0] += count; |
1041 | return 1; |
1098 | return 1; |
1042 | } else { |
1099 | } else { |
1043 | /* |
1100 | /* |
1044 | * The interval doesn't adjoin with the right interval. |
1101 | * The interval doesn't adjoin with the right interval. |
1045 | * It must be added individually. |
1102 | * It must be added individually. |
Line 1068... | Line 1125... | ||
1068 | } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) { |
1125 | } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) { |
1069 | /* The interval intersects with the right interval. */ |
1126 | /* The interval intersects with the right interval. */ |
1070 | return 0; |
1127 | return 0; |
1071 | } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
1128 | } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
1072 | /* The interval can be added by merging the two already present intervals. */ |
1129 | /* The interval can be added by merging the two already present intervals. */ |
1073 | leaf->value[leaf->keys - 1] += (count_t) count + right_cnt; |
1130 | leaf->value[leaf->keys - 1] += count + right_cnt; |
1074 | btree_remove(&a->used_space, right_pg, node); |
1131 | btree_remove(&a->used_space, right_pg, node); |
1075 | return 1; |
1132 | return 1; |
1076 | } else if (page == left_pg + left_cnt*PAGE_SIZE) { |
1133 | } else if (page == left_pg + left_cnt*PAGE_SIZE) { |
1077 | /* The interval can be added by simply growing the left interval. */ |
1134 | /* The interval can be added by simply growing the left interval. */ |
1078 | leaf->value[leaf->keys - 1] += (count_t) count; |
1135 | leaf->value[leaf->keys - 1] += count; |
1079 | return 1; |
1136 | return 1; |
1080 | } else if (page + count*PAGE_SIZE == right_pg) { |
1137 | } else if (page + count*PAGE_SIZE == right_pg) { |
1081 | /* |
1138 | /* |
1082 | * The interval can be addded by simply moving base of the right |
1139 | * The interval can be addded by simply moving base of the right |
1083 | * interval down and increasing its size accordingly. |
1140 | * interval down and increasing its size accordingly. |
1084 | */ |
1141 | */ |
1085 | node->value[0] += (count_t) count; |
1142 | node->value[0] += count; |
1086 | node->key[0] = page; |
1143 | node->key[0] = page; |
1087 | return 1; |
1144 | return 1; |
1088 | } else { |
1145 | } else { |
1089 | /* |
1146 | /* |
1090 | * The interval is between both neigbouring intervals, |
1147 | * The interval is between both neigbouring intervals, |
Line 1101... | Line 1158... | ||
1101 | * Investigate the border case in which the right neighbour does not |
1158 | * Investigate the border case in which the right neighbour does not |
1102 | * exist but the interval fits from the right. |
1159 | * exist but the interval fits from the right. |
1103 | */ |
1160 | */ |
1104 | 1161 | ||
1105 | if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) { |
1162 | if (overlaps(page, count*PAGE_SIZE, left_pg, left_cnt*PAGE_SIZE)) { |
1106 | /* The interval intersects with the right interval. */ |
1163 | /* The interval intersects with the left interval. */ |
1107 | return 0; |
1164 | return 0; |
1108 | } else if (left_pg + left_cnt*PAGE_SIZE == page) { |
1165 | } else if (left_pg + left_cnt*PAGE_SIZE == page) { |
1109 | /* The interval can be added by growing the left interval. */ |
1166 | /* The interval can be added by growing the left interval. */ |
1110 | leaf->value[leaf->keys - 1] += (count_t) count; |
1167 | leaf->value[leaf->keys - 1] += count; |
1111 | return 1; |
1168 | return 1; |
1112 | } else { |
1169 | } else { |
1113 | /* |
1170 | /* |
1114 | * The interval doesn't adjoin with the left interval. |
1171 | * The interval doesn't adjoin with the left interval. |
1115 | * It must be added individually. |
1172 | * It must be added individually. |
Line 1139... | Line 1196... | ||
1139 | } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) { |
1196 | } else if (overlaps(page, count*PAGE_SIZE, right_pg, right_cnt*PAGE_SIZE)) { |
1140 | /* The interval intersects with the right interval. */ |
1197 | /* The interval intersects with the right interval. */ |
1141 | return 0; |
1198 | return 0; |
1142 | } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
1199 | } else if ((page == left_pg + left_cnt*PAGE_SIZE) && (page + count*PAGE_SIZE == right_pg)) { |
1143 | /* The interval can be added by merging the two already present intervals. */ |
1200 | /* The interval can be added by merging the two already present intervals. */ |
1144 | leaf->value[i - 1] += (count_t) count + right_cnt; |
1201 | leaf->value[i - 1] += count + right_cnt; |
1145 | btree_remove(&a->used_space, right_pg, leaf); |
1202 | btree_remove(&a->used_space, right_pg, leaf); |
1146 | return 1; |
1203 | return 1; |
1147 | } else if (page == left_pg + left_cnt*PAGE_SIZE) { |
1204 | } else if (page == left_pg + left_cnt*PAGE_SIZE) { |
1148 | /* The interval can be added by simply growing the left interval. */ |
1205 | /* The interval can be added by simply growing the left interval. */ |
1149 | leaf->value[i - 1] += (count_t) count; |
1206 | leaf->value[i - 1] += count; |
1150 | return 1; |
1207 | return 1; |
1151 | } else if (page + count*PAGE_SIZE == right_pg) { |
1208 | } else if (page + count*PAGE_SIZE == right_pg) { |
1152 | /* |
1209 | /* |
1153 | * The interval can be addded by simply moving base of the right |
1210 | * The interval can be addded by simply moving base of the right |
1154 | * interval down and increasing its size accordingly. |
1211 | * interval down and increasing its size accordingly. |
1155 | */ |
1212 | */ |
1156 | leaf->value[i] += (count_t) count; |
1213 | leaf->value[i] += count; |
1157 | leaf->key[i] = page; |
1214 | leaf->key[i] = page; |
1158 | return 1; |
1215 | return 1; |
1159 | } else { |
1216 | } else { |
1160 | /* |
1217 | /* |
1161 | * The interval is between both neigbouring intervals, |
1218 | * The interval is between both neigbouring intervals, |
Line 1196... | Line 1253... | ||
1196 | */ |
1253 | */ |
1197 | if (count > pages) { |
1254 | if (count > pages) { |
1198 | return 0; |
1255 | return 0; |
1199 | } else if (count == pages) { |
1256 | } else if (count == pages) { |
1200 | btree_remove(&a->used_space, page, leaf); |
1257 | btree_remove(&a->used_space, page, leaf); |
- | 1258 | return 1; |
|
1201 | } else { |
1259 | } else { |
1202 | /* |
1260 | /* |
1203 | * Find the respective interval. |
1261 | * Find the respective interval. |
1204 | * Decrease its size and relocate its start address. |
1262 | * Decrease its size and relocate its start address. |
1205 | */ |
1263 | */ |
1206 | for (i = 0; i < leaf->keys; i++) { |
1264 | for (i = 0; i < leaf->keys; i++) { |
1207 | if (leaf->key[i] == page) { |
1265 | if (leaf->key[i] == page) { |
1208 | leaf->key[i] += count*PAGE_SIZE; |
1266 | leaf->key[i] += count*PAGE_SIZE; |
1209 | leaf->value[i] -= (count_t) count; |
1267 | leaf->value[i] -= count; |
1210 | return 1; |
1268 | return 1; |
1211 | } |
1269 | } |
1212 | } |
1270 | } |
1213 | goto error; |
1271 | goto error; |
1214 | } |
1272 | } |
Line 1224... | Line 1282... | ||
1224 | /* |
1282 | /* |
1225 | * The interval is contained in the rightmost interval |
1283 | * The interval is contained in the rightmost interval |
1226 | * of the left neighbour and can be removed by |
1284 | * of the left neighbour and can be removed by |
1227 | * updating the size of the bigger interval. |
1285 | * updating the size of the bigger interval. |
1228 | */ |
1286 | */ |
1229 | node->value[node->keys - 1] -= (count_t) count; |
1287 | node->value[node->keys - 1] -= count; |
1230 | return 1; |
1288 | return 1; |
1231 | } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
1289 | } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
1232 | count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE); |
1290 | count_t new_cnt; |
1233 | 1291 | ||
1234 | /* |
1292 | /* |
1235 | * The interval is contained in the rightmost interval |
1293 | * The interval is contained in the rightmost interval |
1236 | * of the left neighbour but its removal requires |
1294 | * of the left neighbour but its removal requires |
1237 | * both updating the size of the original interval and |
1295 | * both updating the size of the original interval and |
1238 | * also inserting a new interval. |
1296 | * also inserting a new interval. |
1239 | */ |
1297 | */ |
- | 1298 | new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH; |
|
1240 | node->value[node->keys - 1] -= (count_t) count + new_cnt; |
1299 | node->value[node->keys - 1] -= count + new_cnt; |
1241 | btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
1300 | btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
1242 | return 1; |
1301 | return 1; |
1243 | } |
1302 | } |
1244 | } |
1303 | } |
1245 | return 0; |
1304 | return 0; |
Line 1256... | Line 1315... | ||
1256 | /* |
1315 | /* |
1257 | * The interval is contained in the rightmost interval |
1316 | * The interval is contained in the rightmost interval |
1258 | * of the leaf and can be removed by updating the size |
1317 | * of the leaf and can be removed by updating the size |
1259 | * of the bigger interval. |
1318 | * of the bigger interval. |
1260 | */ |
1319 | */ |
1261 | leaf->value[leaf->keys - 1] -= (count_t) count; |
1320 | leaf->value[leaf->keys - 1] -= count; |
1262 | return 1; |
1321 | return 1; |
1263 | } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
1322 | } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
1264 | count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE); |
1323 | count_t new_cnt; |
1265 | 1324 | ||
1266 | /* |
1325 | /* |
1267 | * The interval is contained in the rightmost interval |
1326 | * The interval is contained in the rightmost interval |
1268 | * of the leaf but its removal requires both updating |
1327 | * of the leaf but its removal requires both updating |
1269 | * the size of the original interval and |
1328 | * the size of the original interval and |
1270 | * also inserting a new interval. |
1329 | * also inserting a new interval. |
1271 | */ |
1330 | */ |
- | 1331 | new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH; |
|
1272 | leaf->value[leaf->keys - 1] -= (count_t) count + new_cnt; |
1332 | leaf->value[leaf->keys - 1] -= count + new_cnt; |
1273 | btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
1333 | btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
1274 | return 1; |
1334 | return 1; |
1275 | } |
1335 | } |
1276 | } |
1336 | } |
1277 | return 0; |
1337 | return 0; |
Line 1294... | Line 1354... | ||
1294 | /* |
1354 | /* |
1295 | * The interval is contained in the interval (i - 1) |
1355 | * The interval is contained in the interval (i - 1) |
1296 | * of the leaf and can be removed by updating the size |
1356 | * of the leaf and can be removed by updating the size |
1297 | * of the bigger interval. |
1357 | * of the bigger interval. |
1298 | */ |
1358 | */ |
1299 | leaf->value[i - 1] -= (count_t) count; |
1359 | leaf->value[i - 1] -= count; |
1300 | return 1; |
1360 | return 1; |
1301 | } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
1361 | } else if (page + count*PAGE_SIZE < left_pg + left_cnt*PAGE_SIZE) { |
1302 | count_t new_cnt = (left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE); |
1362 | count_t new_cnt; |
1303 | 1363 | ||
1304 | /* |
1364 | /* |
1305 | * The interval is contained in the interval (i - 1) |
1365 | * The interval is contained in the interval (i - 1) |
1306 | * of the leaf but its removal requires both updating |
1366 | * of the leaf but its removal requires both updating |
1307 | * the size of the original interval and |
1367 | * the size of the original interval and |
1308 | * also inserting a new interval. |
1368 | * also inserting a new interval. |
1309 | */ |
1369 | */ |
- | 1370 | new_cnt = ((left_pg + left_cnt*PAGE_SIZE) - (page + count*PAGE_SIZE)) >> PAGE_WIDTH; |
|
1310 | leaf->value[i - 1] -= (count_t) count + new_cnt; |
1371 | leaf->value[i - 1] -= count + new_cnt; |
1311 | btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
1372 | btree_insert(&a->used_space, page + count*PAGE_SIZE, (void *) new_cnt, leaf); |
1312 | return 1; |
1373 | return 1; |
1313 | } |
1374 | } |
1314 | } |
1375 | } |
1315 | return 0; |
1376 | return 0; |