← Back to branch summary

~helenos-nicf/helenos/nicf

« back to all changes in this revision

Viewing changes to kernel/generic/src/mm/as.c

  • Committer: Radim Vansa
  • Date: 2011-09-20 21:55:59 UTC
  • mfrom: (697.1.517 HelenOS.mainline)
  • Revision ID: radim.vansa@matfyz.cz-20110920215559-7fjpai6wt5ieurcq
Merge with mainline

Show diffs side-by-side

added added

removed removed

Lines of Context:
kernel/generic/src/mm/as.c
95
95
/** ASID subsystem lock.
96
96
 *
97
97
 * This lock protects:
98
 
 * - inactive_as_with_asid_head list
 
98
 * - inactive_as_with_asid_list
99
99
 * - as->asid for each as of the as_t type
100
100
 * - asids_allocated counter
101
101
 *
106
106
 * Inactive address spaces (on all processors)
107
107
 * that have valid ASID.
108
108
 */
109
 
LIST_INITIALIZE( inactive_as_with_asid_head);
 
109
LIST_INITIALIZE(inactive_as_with_asid_list);
110
110
 
111
111
/** Kernel address space. */
112
112
as_t *AS_KERNEL = NULL;
234
234
         */
235
235
        bool cond = true;
236
236
        while (cond) {
237
 
                ASSERT(!list_empty(&as->as_area_btree.leaf_head));
238
 
 
239
 
                btree_node_t *node = list_get_instance(
240
 
                    as->as_area_btree.leaf_head.next, btree_node_t, leaf_link);
241
 
 
 
237
                ASSERT(!list_empty(&as->as_area_btree.leaf_list));
 
238
                
 
239
                btree_node_t *node =
 
240
                    list_get_instance(list_first(&as->as_area_btree.leaf_list),
 
241
                    btree_node_t, leaf_link);
 
242
                
242
243
                if ((cond = node->keys))
243
244
                        as_area_destroy(as, node->key[0]);
244
245
        }
300
301
        /*
301
302
         * We don't want any area to have conflicts with NULL page.
302
303
         */
303
 
        if (overlaps(addr, count << PAGE_WIDTH, (uintptr_t) NULL, PAGE_SIZE))
 
304
        if (overlaps(addr, P2SZ(count), (uintptr_t) NULL, PAGE_SIZE))
304
305
                return false;
305
306
 
306
307
        /*
326
327
 
327
328
                if (area != avoid) {
328
329
                        mutex_lock(&area->lock);
329
 
 
330
 
                        if (overlaps(addr, count << PAGE_WIDTH, area->base, area->pages
331
 
                            << PAGE_WIDTH)) {
 
330
                        
 
331
                        if (overlaps(addr, P2SZ(count), area->base,
 
332
                            P2SZ(area->pages))) {
332
333
                                mutex_unlock(&area->lock);
333
334
                                return false;
334
335
                        }
343
344
 
344
345
                if (area != avoid) {
345
346
                        mutex_lock(&area->lock);
346
 
 
347
 
                        if (overlaps(addr, count << PAGE_WIDTH, area->base, area->pages
348
 
                            << PAGE_WIDTH)) {
 
347
                        
 
348
                        if (overlaps(addr, P2SZ(count), area->base,
 
349
                            P2SZ(area->pages))) {
349
350
                                mutex_unlock(&area->lock);
350
351
                                return false;
351
352
                        }
363
364
                        continue;
364
365
 
365
366
                mutex_lock(&area->lock);
366
 
 
367
 
                if (overlaps(addr, count << PAGE_WIDTH, area->base, area->pages
368
 
                    << PAGE_WIDTH)) {
 
367
                
 
368
                if (overlaps(addr, P2SZ(count), area->base,
 
369
                    P2SZ(area->pages))) {
369
370
                        mutex_unlock(&area->lock);
370
371
                        return false;
371
372
                }
378
379
         * Check if it doesn't conflict with kernel address space.
379
380
         */
380
381
        if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
381
 
                return !overlaps(addr, count << PAGE_WIDTH, KERNEL_ADDRESS_SPACE_START,
 
382
                return !overlaps(addr, P2SZ(count), KERNEL_ADDRESS_SPACE_START,
382
383
                    KERNEL_ADDRESS_SPACE_END - KERNEL_ADDRESS_SPACE_START);
383
384
        }
384
385
 
473
474
        ASSERT(mutex_locked(&as->lock));
474
475
 
475
476
        btree_node_t *leaf;
476
 
        as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
 
477
        as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va,
 
478
            &leaf);
477
479
        if (area) {
478
480
                /* va is the base address of an address space area */
479
481
                mutex_lock(&area->lock);
481
483
        }
482
484
 
483
485
        /*
484
 
         * Search the leaf node and the righmost record of its left neighbour
 
486
         * Search the leaf node and the rightmost record of its left neighbour
485
487
         * to find out whether this is a miss or va belongs to an address
486
488
         * space area found there.
487
489
         */
494
496
 
495
497
                mutex_lock(&area->lock);
496
498
 
497
 
                if ((area->base <= va) && (va < area->base
498
 
                    + (area->pages << PAGE_WIDTH)))
 
499
                if ((area->base <= va) &&
 
500
                    (va <= area->base + (P2SZ(area->pages) - 1)))
499
501
                        return area;
500
502
 
501
503
                mutex_unlock(&area->lock);
511
513
                area = (as_area_t *) lnode->value[lnode->keys - 1];
512
514
 
513
515
                mutex_lock(&area->lock);
514
 
 
515
 
                if (va < area->base + (area->pages << PAGE_WIDTH))
 
516
                
 
517
                if (va <= area->base + (P2SZ(area->pages) - 1))
516
518
                        return area;
517
519
 
518
520
                mutex_unlock(&area->lock);
588
590
        }
589
591
 
590
592
        if (pages < area->pages) {
591
 
                uintptr_t start_free = area->base + (pages << PAGE_WIDTH);
592
 
 
 
593
                uintptr_t start_free = area->base + P2SZ(pages);
 
594
                
593
595
                /*
594
596
                 * Shrinking the area.
595
597
                 * No need to check for overlaps.
600
602
                /*
601
603
                 * Start TLB shootdown sequence.
602
604
                 */
603
 
                ipl_t ipl = tlb_shootdown_start(TLB_INVL_PAGES, as->asid, area->base
604
 
                    + (pages << PAGE_WIDTH), area->pages - pages);
605
 
 
 
605
                ipl_t ipl = tlb_shootdown_start(TLB_INVL_PAGES, as->asid,
 
606
                    area->base + P2SZ(pages), area->pages - pages);
 
607
                
606
608
                /*
607
609
                 * Remove frames belonging to used space starting from
608
610
                 * the highest addresses downwards until an overlap with
612
614
                 */
613
615
                bool cond = true;
614
616
                while (cond) {
615
 
                        ASSERT(!list_empty(&area->used_space.leaf_head));
616
 
 
617
 
                        btree_node_t *node = list_get_instance(
618
 
                            area->used_space.leaf_head.prev, btree_node_t, leaf_link);
619
 
 
 
617
                        ASSERT(!list_empty(&area->used_space.leaf_list));
 
618
                        
 
619
                        btree_node_t *node =
 
620
                            list_get_instance(list_last(&area->used_space.leaf_list),
 
621
                            btree_node_t, leaf_link);
 
622
                        
620
623
                        if ((cond = (bool) node->keys)) {
621
624
                                uintptr_t ptr = node->key[node->keys - 1];
622
625
                                size_t size = (size_t) node->value[node->keys - 1];
623
626
                                size_t i = 0;
624
 
 
625
 
                                if (overlaps(ptr, size << PAGE_WIDTH, area->base, pages
626
 
                                    << PAGE_WIDTH)) {
627
 
 
628
 
                                        if (ptr + (size << PAGE_WIDTH) <= start_free) {
 
627
                                
 
628
                                if (overlaps(ptr, P2SZ(size), area->base,
 
629
                                    P2SZ(pages))) {
 
630
                                        
 
631
                                        if (ptr + P2SZ(size) <= start_free) {
629
632
                                                /*
630
633
                                                 * The whole interval fits
631
634
                                                 * completely in the resized
655
658
                                }
656
659
 
657
660
                                for (; i < size; i++) {
658
 
                                        pte_t *pte = page_mapping_find(as, ptr + (i << PAGE_WIDTH));
659
 
 
 
661
                                        pte_t *pte = page_mapping_find(as,
 
662
                                            ptr + P2SZ(i), false);
 
663
                                        
660
664
                                        ASSERT(pte);
661
665
                                        ASSERT(PTE_VALID(pte));
662
666
                                        ASSERT(PTE_PRESENT(pte));
663
667
 
664
668
                                        if ((area->backend) && (area->backend->frame_free)) {
665
669
                                                area->backend->frame_free(area,
666
 
                                                    ptr + (i << PAGE_WIDTH), PTE_GET_FRAME(pte));
 
670
                                                    ptr + P2SZ(i),
 
671
                                                    PTE_GET_FRAME(pte));
667
672
                                        }
668
 
 
669
 
                                        page_mapping_remove(as, ptr + (i << PAGE_WIDTH));
 
673
                                        
 
674
                                        page_mapping_remove(as, ptr + P2SZ(i));
670
675
                                }
671
676
                        }
672
677
                }
674
679
                /*
675
680
                 * Finish TLB shootdown sequence.
676
681
                 */
677
 
 
678
 
                tlb_invalidate_pages(as->asid, area->base + (pages << PAGE_WIDTH),
 
682
                
 
683
                tlb_invalidate_pages(as->asid, area->base + P2SZ(pages),
679
684
                    area->pages - pages);
680
685
 
681
686
                /*
682
 
                 * Invalidate software translation caches (e.g. TSB on sparc64).
 
687
                 * Invalidate software translation caches
 
688
                 * (e.g. TSB on sparc64, PHT on ppc32).
683
689
                 */
684
 
                as_invalidate_translation_cache(as, area->base + (pages << PAGE_WIDTH),
 
690
                as_invalidate_translation_cache(as, area->base + P2SZ(pages),
685
691
                    area->pages - pages);
686
692
                tlb_shootdown_finalize(ipl);
687
693
 
734
740
                        sh_info->backend->share_finish(sh_info);
735
741
                } else {
736
742
                        dealloc = true;
737
 
                        link_t *cur;
738
743
 
739
744
                        /*
740
745
                         * Now walk carefully the pagemap B+tree and free/remove
741
746
                         * reference from all frames found there.
742
747
                         */
743
 
                        for (cur = sh_info->pagemap.leaf_head.next; cur
744
 
                            != &sh_info->pagemap.leaf_head; cur = cur->next) {
745
 
                                btree_node_t *node = list_get_instance(cur, btree_node_t,
746
 
                                    leaf_link);
 
748
                        list_foreach(sh_info->pagemap.leaf_list, cur) {
 
749
                                btree_node_t *node
 
750
                                        = list_get_instance(cur, btree_node_t, leaf_link);
747
751
                                btree_key_t i;
748
752
 
749
753
                                for (i = 0; i < node->keys; i++)
807
811
        /*
808
812
         * Visit only the pages mapped by used_space B+tree.
809
813
         */
810
 
        link_t *cur;
811
 
        for (cur = area->used_space.leaf_head.next; cur
812
 
            != &area->used_space.leaf_head; cur = cur->next) {
813
 
                btree_node_t * node;
 
814
        list_foreach(area->used_space.leaf_list, cur) {
 
815
                btree_node_t *node;
814
816
                btree_key_t i;
815
817
 
816
818
                node = list_get_instance(cur, btree_node_t, leaf_link);
819
821
                        size_t size;
820
822
 
821
823
                        for (size = 0; size < (size_t) node->value[i]; size++) {
822
 
                                pte_t *pte = page_mapping_find(as, ptr + (size << PAGE_WIDTH));
823
 
 
 
824
                                pte_t *pte = page_mapping_find(as,
 
825
                                     ptr + P2SZ(size), false);
 
826
                                
824
827
                                ASSERT(pte);
825
828
                                ASSERT(PTE_VALID(pte));
826
829
                                ASSERT(PTE_PRESENT(pte));
827
 
 
828
 
                                if ((area->backend) && (area->backend->frame_free)) {
829
 
                                        area->backend->frame_free(area, ptr + (size << PAGE_WIDTH),
 
830
                                
 
831
                                if ((area->backend) &&
 
832
                                    (area->backend->frame_free)) {
 
833
                                        area->backend->frame_free(area,
 
834
                                            ptr + P2SZ(size),
830
835
                                            PTE_GET_FRAME(pte));
831
836
                                }
832
 
 
833
 
                                page_mapping_remove(as, ptr + (size << PAGE_WIDTH));
 
837
                                
 
838
                                page_mapping_remove(as, ptr + P2SZ(size));
834
839
                        }
835
840
                }
836
841
        }
842
847
        tlb_invalidate_pages(as->asid, area->base, area->pages);
843
848
 
844
849
        /*
845
 
         * Invalidate potential software translation caches (e.g. TSB on
846
 
         * sparc64).
 
850
         * Invalidate potential software translation caches
 
851
         * (e.g. TSB on sparc64, PHT on ppc32).
847
852
         */
848
853
        as_invalidate_translation_cache(as, area->base, area->pages);
849
854
        tlb_shootdown_finalize(ipl);
916
921
                mutex_unlock(&src_as->lock);
917
922
                return ENOTSUP;
918
923
        }
919
 
 
920
 
        size_t src_size = src_area->pages << PAGE_WIDTH;
 
924
        
 
925
        size_t src_size = P2SZ(src_area->pages);
921
926
        unsigned int src_flags = src_area->flags;
922
927
        mem_backend_t *src_backend = src_area->backend;
923
928
        mem_backend_data_t src_backend_data = src_area->backend_data;
1084
1089
         * Compute total number of used pages in the used_space B+tree
1085
1090
         */
1086
1091
        size_t used_pages = 0;
1087
 
        link_t *cur;
1088
 
 
1089
 
        for (cur = area->used_space.leaf_head.next; cur
1090
 
            != &area->used_space.leaf_head; cur = cur->next) {
1091
 
                btree_node_t *node = list_get_instance(cur, btree_node_t, leaf_link);
 
1092
        
 
1093
        list_foreach(area->used_space.leaf_list, cur) {
 
1094
                btree_node_t *node
 
1095
                    = list_get_instance(cur, btree_node_t, leaf_link);
1092
1096
                btree_key_t i;
1093
1097
 
1094
1098
                for (i = 0; i < node->keys; i++)
1111
1115
         * numbers.
1112
1116
         */
1113
1117
        size_t frame_idx = 0;
1114
 
 
1115
 
        for (cur = area->used_space.leaf_head.next; cur
1116
 
            != &area->used_space.leaf_head; cur = cur->next) {
1117
 
                btree_node_t *node = list_get_instance(cur, btree_node_t, leaf_link);
 
1118
        
 
1119
        list_foreach(area->used_space.leaf_list, cur) {
 
1120
                btree_node_t *node = list_get_instance(cur, btree_node_t,
 
1121
                    leaf_link);
1118
1122
                btree_key_t i;
1119
1123
 
1120
1124
                for (i = 0; i < node->keys; i++) {
1122
1126
                        size_t size;
1123
1127
 
1124
1128
                        for (size = 0; size < (size_t) node->value[i]; size++) {
1125
 
                                pte_t *pte = page_mapping_find(as, ptr + (size << PAGE_WIDTH));
1126
 
 
 
1129
                                pte_t *pte = page_mapping_find(as,
 
1130
                                    ptr + P2SZ(size), false);
 
1131
                                
1127
1132
                                ASSERT(pte);
1128
1133
                                ASSERT(PTE_VALID(pte));
1129
1134
                                ASSERT(PTE_PRESENT(pte));
1131
1136
                                old_frame[frame_idx++] = PTE_GET_FRAME(pte);
1132
1137
 
1133
1138
                                /* Remove old mapping */
1134
 
                                page_mapping_remove(as, ptr + (size << PAGE_WIDTH));
 
1139
                                page_mapping_remove(as, ptr + P2SZ(size));
1135
1140
                        }
1136
1141
                }
1137
1142
        }
1143
1148
        tlb_invalidate_pages(as->asid, area->base, area->pages);
1144
1149
 
1145
1150
        /*
1146
 
         * Invalidate potential software translation caches (e.g. TSB on
1147
 
         * sparc64).
 
1151
         * Invalidate potential software translation caches
 
1152
         * (e.g. TSB on sparc64, PHT on ppc32).
1148
1153
         */
1149
1154
        as_invalidate_translation_cache(as, area->base, area->pages);
1150
1155
        tlb_shootdown_finalize(ipl);
1162
1167
         * the new flags at once.
1163
1168
         */
1164
1169
        frame_idx = 0;
1165
 
 
1166
 
        for (cur = area->used_space.leaf_head.next; cur
1167
 
            != &area->used_space.leaf_head; cur = cur->next) {
1168
 
                btree_node_t *node = list_get_instance(cur, btree_node_t, leaf_link);
 
1170
        
 
1171
        list_foreach(area->used_space.leaf_list, cur) {
 
1172
                btree_node_t *node
 
1173
                    = list_get_instance(cur, btree_node_t, leaf_link);
1169
1174
                btree_key_t i;
1170
1175
 
1171
1176
                for (i = 0; i < node->keys; i++) {
1176
1181
                                page_table_lock(as, false);
1177
1182
 
1178
1183
                                /* Insert the new mapping */
1179
 
                                page_mapping_insert(as, ptr + (size << PAGE_WIDTH),
 
1184
                                page_mapping_insert(as, ptr + P2SZ(size),
1180
1185
                                    old_frame[frame_idx++], page_flags);
1181
1186
 
1182
1187
                                page_table_unlock(as, false);
1257
1262
         * we need to make sure the mapping has not been already inserted.
1258
1263
         */
1259
1264
        pte_t *pte;
1260
 
        if ((pte = page_mapping_find(AS, page))) {
 
1265
        if ((pte = page_mapping_find(AS, page, false))) {
1261
1266
                if (PTE_PRESENT(pte)) {
1262
1267
                        if (((access == PF_ACCESS_READ) && PTE_READABLE(pte)) || (access
1263
1268
                            == PF_ACCESS_WRITE && PTE_WRITABLE(pte)) || (access
1306
1311
 * scheduling. Sleeping here would lead to deadlock on wakeup. Another
1307
1312
 * thing which is forbidden in this context is locking the address space.
1308
1313
 *
1309
 
 * When this function is enetered, no spinlocks may be held.
 
1314
 * When this function is entered, no spinlocks may be held.
1310
1315
 *
1311
1316
 * @param old Old address space or NULL.
1312
1317
 * @param new New address space.
1347
1352
                        ASSERT(old_as->asid != ASID_INVALID);
1348
1353
 
1349
1354
                        list_append(&old_as->inactive_as_with_asid_link,
1350
 
                            &inactive_as_with_asid_head);
 
1355
                            &inactive_as_with_asid_list);
1351
1356
                }
1352
1357
 
1353
1358
                /*
1496
1501
        as_area_t *src_area = as_find_area_and_lock(AS, base);
1497
1502
 
1498
1503
        if (src_area) {
1499
 
                size = src_area->pages << PAGE_WIDTH;
 
1504
                size = P2SZ(src_area->pages);
1500
1505
                mutex_unlock(&src_area->lock);
1501
1506
        } else
1502
1507
                size = 0;
1552
1557
 
1553
1558
                if (page >= right_pg) {
1554
1559
                        /* Do nothing. */
1555
 
                } else if (overlaps(page, count << PAGE_WIDTH, left_pg, left_cnt
1556
 
                    << PAGE_WIDTH)) {
 
1560
                } else if (overlaps(page, P2SZ(count), left_pg,
 
1561
                    P2SZ(left_cnt))) {
1557
1562
                        /* The interval intersects with the left interval. */
1558
1563
                        return false;
1559
 
                } else if (overlaps(page, count << PAGE_WIDTH, right_pg, right_cnt
1560
 
                    << PAGE_WIDTH)) {
 
1564
                } else if (overlaps(page, P2SZ(count), right_pg,
 
1565
                    P2SZ(right_cnt))) {
1561
1566
                        /* The interval intersects with the right interval. */
1562
1567
                        return false;
1563
 
                } else if ((page == left_pg + (left_cnt << PAGE_WIDTH)) && (page
1564
 
                    + (count << PAGE_WIDTH) == right_pg)) {
 
1568
                } else if ((page == left_pg + P2SZ(left_cnt)) &&
 
1569
                    (page + P2SZ(count) == right_pg)) {
1565
1570
                        /*
1566
1571
                         * The interval can be added by merging the two already
1567
1572
                         * present intervals.
1569
1574
                        node->value[node->keys - 1] += count + right_cnt;
1570
1575
                        btree_remove(&area->used_space, right_pg, leaf);
1571
1576
                        goto success;
1572
 
                } else if (page == left_pg + (left_cnt << PAGE_WIDTH)) {
 
1577
                } else if (page == left_pg + P2SZ(left_cnt)) {
1573
1578
                        /*
1574
1579
                         * The interval can be added by simply growing the left
1575
1580
                         * interval.
1576
1581
                         */
1577
1582
                        node->value[node->keys - 1] += count;
1578
1583
                        goto success;
1579
 
                } else if (page + (count << PAGE_WIDTH) == right_pg) {
 
1584
                } else if (page + P2SZ(count) == right_pg) {
1580
1585
                        /*
1581
1586
                         * The interval can be addded by simply moving base of
1582
1587
                         * the right interval down and increasing its size
1601
1606
                 * Investigate the border case in which the left neighbour does
1602
1607
                 * not exist but the interval fits from the left.
1603
1608
                 */
1604
 
 
1605
 
                if (overlaps(page, count << PAGE_WIDTH, right_pg, right_cnt
1606
 
                    << PAGE_WIDTH)) {
 
1609
                
 
1610
                if (overlaps(page, P2SZ(count), right_pg, P2SZ(right_cnt))) {
1607
1611
                        /* The interval intersects with the right interval. */
1608
1612
                        return false;
1609
 
                } else if (page + (count << PAGE_WIDTH) == right_pg) {
 
1613
                } else if (page + P2SZ(count) == right_pg) {
1610
1614
                        /*
1611
1615
                         * The interval can be added by moving the base of the
1612
1616
                         * right interval down and increasing its size
1640
1644
 
1641
1645
                if (page < left_pg) {
1642
1646
                        /* Do nothing. */
1643
 
                } else if (overlaps(page, count << PAGE_WIDTH, left_pg, left_cnt
1644
 
                    << PAGE_WIDTH)) {
 
1647
                } else if (overlaps(page, P2SZ(count), left_pg,
 
1648
                    P2SZ(left_cnt))) {
1645
1649
                        /* The interval intersects with the left interval. */
1646
1650
                        return false;
1647
 
                } else if (overlaps(page, count << PAGE_WIDTH, right_pg, right_cnt
1648
 
                    << PAGE_WIDTH)) {
 
1651
                } else if (overlaps(page, P2SZ(count), right_pg,
 
1652
                    P2SZ(right_cnt))) {
1649
1653
                        /* The interval intersects with the right interval. */
1650
1654
                        return false;
1651
 
                } else if ((page == left_pg + (left_cnt << PAGE_WIDTH)) && (page
1652
 
                    + (count << PAGE_WIDTH) == right_pg)) {
 
1655
                } else if ((page == left_pg + P2SZ(left_cnt)) &&
 
1656
                    (page + P2SZ(count) == right_pg)) {
1653
1657
                        /*
1654
1658
                         * The interval can be added by merging the two already
1655
1659
                         * present intervals.
1657
1661
                        leaf->value[leaf->keys - 1] += count + right_cnt;
1658
1662
                        btree_remove(&area->used_space, right_pg, node);
1659
1663
                        goto success;
1660
 
                } else if (page == left_pg + (left_cnt << PAGE_WIDTH)) {
 
1664
                } else if (page == left_pg + P2SZ(left_cnt)) {
1661
1665
                        /*
1662
1666
                         * The interval can be added by simply growing the left
1663
1667
                         * interval.
1664
1668
                         */
1665
1669
                        leaf->value[leaf->keys - 1] += count;
1666
1670
                        goto success;
1667
 
                } else if (page + (count << PAGE_WIDTH) == right_pg) {
 
1671
                } else if (page + P2SZ(count) == right_pg) {
1668
1672
                        /*
1669
1673
                         * The interval can be addded by simply moving base of
1670
1674
                         * the right interval down and increasing its size
1689
1693
                 * Investigate the border case in which the right neighbour
1690
1694
                 * does not exist but the interval fits from the right.
1691
1695
                 */
1692
 
 
1693
 
                if (overlaps(page, count << PAGE_WIDTH, left_pg, left_cnt << PAGE_WIDTH)) {
 
1696
                
 
1697
                if (overlaps(page, P2SZ(count), left_pg, P2SZ(left_cnt))) {
1694
1698
                        /* The interval intersects with the left interval. */
1695
1699
                        return false;
1696
 
                } else if (left_pg + (left_cnt << PAGE_WIDTH) == page) {
 
1700
                } else if (left_pg + P2SZ(left_cnt) == page) {
1697
1701
                        /*
1698
1702
                         * The interval can be added by growing the left
1699
1703
                         * interval.
1726
1730
                        /*
1727
1731
                         * The interval fits between left_pg and right_pg.
1728
1732
                         */
1729
 
 
1730
 
                        if (overlaps(page, count << PAGE_WIDTH, left_pg, left_cnt
1731
 
                            << PAGE_WIDTH)) {
 
1733
                        
 
1734
                        if (overlaps(page, P2SZ(count), left_pg,
 
1735
                            P2SZ(left_cnt))) {
1732
1736
                                /*
1733
1737
                                 * The interval intersects with the left
1734
1738
                                 * interval.
1735
1739
                                 */
1736
1740
                                return false;
1737
 
                        } else if (overlaps(page, count << PAGE_WIDTH, right_pg, right_cnt
1738
 
                            << PAGE_WIDTH)) {
 
1741
                        } else if (overlaps(page, P2SZ(count), right_pg,
 
1742
                            P2SZ(right_cnt))) {
1739
1743
                                /*
1740
1744
                                 * The interval intersects with the right
1741
1745
                                 * interval.
1742
1746
                                 */
1743
1747
                                return false;
1744
 
                        } else if ((page == left_pg + (left_cnt << PAGE_WIDTH)) && (page
1745
 
                            + (count << PAGE_WIDTH) == right_pg)) {
 
1748
                        } else if ((page == left_pg + P2SZ(left_cnt)) &&
 
1749
                            (page + P2SZ(count) == right_pg)) {
1746
1750
                                /*
1747
1751
                                 * The interval can be added by merging the two
1748
1752
                                 * already present intervals.
1750
1754
                                leaf->value[i - 1] += count + right_cnt;
1751
1755
                                btree_remove(&area->used_space, right_pg, leaf);
1752
1756
                                goto success;
1753
 
                        } else if (page == left_pg + (left_cnt << PAGE_WIDTH)) {
 
1757
                        } else if (page == left_pg + P2SZ(left_cnt)) {
1754
1758
                                /*
1755
1759
                                 * The interval can be added by simply growing
1756
1760
                                 * the left interval.
1757
1761
                                 */
1758
1762
                                leaf->value[i - 1] += count;
1759
1763
                                goto success;
1760
 
                        } else if (page + (count << PAGE_WIDTH) == right_pg) {
 
1764
                        } else if (page + P2SZ(count) == right_pg) {
1761
1765
                                /*
1762
1766
                                 * The interval can be addded by simply moving
1763
1767
                                 * base of the right interval down and
1821
1825
                        btree_key_t i;
1822
1826
                        for (i = 0; i < leaf->keys; i++) {
1823
1827
                                if (leaf->key[i] == page) {
1824
 
                                        leaf->key[i] += count << PAGE_WIDTH;
 
1828
                                        leaf->key[i] += P2SZ(count);
1825
1829
                                        leaf->value[i] -= count;
1826
1830
                                        goto success;
1827
1831
                                }
1830
1834
                        goto error;
1831
1835
                }
1832
1836
        }
1833
 
 
1834
 
        btree_node_t *node =
1835
 
            btree_leaf_node_left_neighbour(&area->used_space, leaf);
 
1837
        
 
1838
        btree_node_t *node = btree_leaf_node_left_neighbour(&area->used_space,
 
1839
            leaf);
1836
1840
        if ((node) && (page < leaf->key[0])) {
1837
1841
                uintptr_t left_pg = node->key[node->keys - 1];
1838
1842
                size_t left_cnt = (size_t) node->value[node->keys - 1];
1839
 
 
1840
 
                if (overlaps(left_pg, left_cnt << PAGE_WIDTH, page, count << PAGE_WIDTH)) {
1841
 
                        if (page + (count << PAGE_WIDTH) == left_pg + (left_cnt
1842
 
                            << PAGE_WIDTH)) {
 
1843
                
 
1844
                if (overlaps(left_pg, P2SZ(left_cnt), page, P2SZ(count))) {
 
1845
                        if (page + P2SZ(count) == left_pg + P2SZ(left_cnt)) {
1843
1846
                                /*
1844
1847
                                 * The interval is contained in the rightmost
1845
1848
                                 * interval of the left neighbour and can be
1848
1851
                                 */
1849
1852
                                node->value[node->keys - 1] -= count;
1850
1853
                                goto success;
1851
 
                        } else if (page + (count << PAGE_WIDTH) < left_pg + (left_cnt
1852
 
                            << PAGE_WIDTH)) {
 
1854
                        } else if (page + P2SZ(count) <
 
1855
                            left_pg + P2SZ(left_cnt)) {
 
1856
                                size_t new_cnt;
 
1857
 
1853
1858
                                /*
1854
1859
                                 * The interval is contained in the rightmost
1855
1860
                                 * interval of the left neighbour but its
1857
1862
                                 * the original interval and also inserting a
1858
1863
                                 * new interval.
1859
1864
                                 */
1860
 
                                size_t new_cnt = ((left_pg + (left_cnt << PAGE_WIDTH)) - (page
1861
 
                                    + (count << PAGE_WIDTH))) >> PAGE_WIDTH;
 
1865
                                new_cnt = ((left_pg + P2SZ(left_cnt)) -
 
1866
                                    (page + P2SZ(count))) >> PAGE_WIDTH;
1862
1867
                                node->value[node->keys - 1] -= count + new_cnt;
1863
 
                                btree_insert(&area->used_space, page + (count << PAGE_WIDTH),
1864
 
                                    (void *) new_cnt, leaf);
 
1868
                                btree_insert(&area->used_space, page +
 
1869
                                    P2SZ(count), (void *) new_cnt, leaf);
1865
1870
                                goto success;
1866
1871
                        }
1867
1872
                }
1873
1878
        if (page > leaf->key[leaf->keys - 1]) {
1874
1879
                uintptr_t left_pg = leaf->key[leaf->keys - 1];
1875
1880
                size_t left_cnt = (size_t) leaf->value[leaf->keys - 1];
1876
 
 
1877
 
                if (overlaps(left_pg, left_cnt << PAGE_WIDTH, page, count << PAGE_WIDTH)) {
1878
 
                        if (page + (count << PAGE_WIDTH) == left_pg + (left_cnt
1879
 
                            << PAGE_WIDTH)) {
 
1881
                
 
1882
                if (overlaps(left_pg, P2SZ(left_cnt), page, P2SZ(count))) {
 
1883
                        if (page + P2SZ(count) == left_pg + P2SZ(left_cnt)) {
1880
1884
                                /*
1881
1885
                                 * The interval is contained in the rightmost
1882
1886
                                 * interval of the leaf and can be removed by
1884
1888
                                 */
1885
1889
                                leaf->value[leaf->keys - 1] -= count;
1886
1890
                                goto success;
1887
 
                        } else if (page + (count << PAGE_WIDTH) < left_pg + (left_cnt
1888
 
                            << PAGE_WIDTH)) {
 
1891
                        } else if (page + P2SZ(count) < left_pg +
 
1892
                            P2SZ(left_cnt)) {
 
1893
                                size_t new_cnt;
 
1894
 
1889
1895
                                /*
1890
1896
                                 * The interval is contained in the rightmost
1891
1897
                                 * interval of the leaf but its removal
1893
1899
                                 * original interval and also inserting a new
1894
1900
                                 * interval.
1895
1901
                                 */
1896
 
                                size_t new_cnt = ((left_pg + (left_cnt << PAGE_WIDTH)) - (page
1897
 
                                    + (count << PAGE_WIDTH))) >> PAGE_WIDTH;
 
1902
                                new_cnt = ((left_pg + P2SZ(left_cnt)) -
 
1903
                                    (page + P2SZ(count))) >> PAGE_WIDTH;
1898
1904
                                leaf->value[leaf->keys - 1] -= count + new_cnt;
1899
 
                                btree_insert(&area->used_space, page + (count << PAGE_WIDTH),
1900
 
                                    (void *) new_cnt, leaf);
 
1905
                                btree_insert(&area->used_space, page +
 
1906
                                    P2SZ(count), (void *) new_cnt, leaf);
1901
1907
                                goto success;
1902
1908
                        }
1903
1909
                }
1919
1925
                         * Now the interval is between intervals corresponding
1920
1926
                         * to (i - 1) and i.
1921
1927
                         */
1922
 
                        if (overlaps(left_pg, left_cnt << PAGE_WIDTH, page, count
1923
 
                            << PAGE_WIDTH)) {
1924
 
                                if (page + (count << PAGE_WIDTH) == left_pg + (left_cnt
1925
 
                                    << PAGE_WIDTH)) {
 
1928
                        if (overlaps(left_pg, P2SZ(left_cnt), page,
 
1929
                            P2SZ(count))) {
 
1930
                                if (page + P2SZ(count) ==
 
1931
                                    left_pg + P2SZ(left_cnt)) {
1926
1932
                                        /*
1927
1933
                                         * The interval is contained in the
1928
1934
                                         * interval (i - 1) of the leaf and can
1931
1937
                                         */
1932
1938
                                        leaf->value[i - 1] -= count;
1933
1939
                                        goto success;
1934
 
                                } else if (page + (count << PAGE_WIDTH) < left_pg + (left_cnt
1935
 
                                    << PAGE_WIDTH)) {
 
1940
                                } else if (page + P2SZ(count) <
 
1941
                                    left_pg + P2SZ(left_cnt)) {
 
1942
                                        size_t new_cnt;
 
1943
 
1936
1944
                                        /*
1937
1945
                                         * The interval is contained in the
1938
1946
                                         * interval (i - 1) of the leaf but its
1940
1948
                                         * size of the original interval and
1941
1949
                                         * also inserting a new interval.
1942
1950
                                         */
1943
 
                                        size_t new_cnt = ((left_pg + (left_cnt << PAGE_WIDTH))
1944
 
                                            - (page + (count << PAGE_WIDTH))) >> PAGE_WIDTH;
 
1951
                                        new_cnt = ((left_pg + P2SZ(left_cnt)) -
 
1952
                                            (page + P2SZ(count))) >>
 
1953
                                            PAGE_WIDTH;
1945
1954
                                        leaf->value[i - 1] -= count + new_cnt;
1946
 
                                        btree_insert(&area->used_space, page
1947
 
                                            + (count << PAGE_WIDTH), (void *) new_cnt, leaf);
 
1955
                                        btree_insert(&area->used_space, page +
 
1956
                                            P2SZ(count), (void *) new_cnt,
 
1957
                                            leaf);
1948
1958
                                        goto success;
1949
1959
                                }
1950
1960
                        }
2027
2037
                ret = addr;
2028
2038
 
2029
2039
        /* Eventually check the addresses behind each area */
2030
 
        link_t *cur;
2031
 
        for (cur = AS->as_area_btree.leaf_head.next; (ret == 0) && (cur
2032
 
            != &AS->as_area_btree.leaf_head); cur = cur->next) {
2033
 
                btree_node_t *node = list_get_instance(cur, btree_node_t, leaf_link);
2034
 
 
 
2040
        list_foreach(AS->as_area_btree.leaf_list, cur) {
 
2041
                if (ret != 0)
 
2042
                        break;
 
2043
                btree_node_t *node =
 
2044
                    list_get_instance(cur, btree_node_t, leaf_link);
 
2045
                
2035
2046
                btree_key_t i;
2036
2047
                for (i = 0; (ret == 0) && (i < node->keys); i++) {
 
2048
                        uintptr_t addr;
 
2049
 
2037
2050
                        as_area_t *area = (as_area_t *) node->value[i];
2038
2051
 
2039
2052
                        mutex_lock(&area->lock);
2040
 
 
2041
 
                        uintptr_t addr = ALIGN_UP(area->base + (area->pages << PAGE_WIDTH),
 
2053
                        
 
2054
                        addr = ALIGN_UP(area->base + P2SZ(area->pages),
2042
2055
                            PAGE_SIZE);
2043
2056
 
2044
2057
                        if ((addr >= base) && (addr >= area->base)
2068
2081
        /* First pass, count number of areas. */
2069
2082
 
2070
2083
        size_t area_cnt = 0;
2071
 
        link_t *cur;
2072
 
 
2073
 
        for (cur = as->as_area_btree.leaf_head.next; cur
2074
 
            != &as->as_area_btree.leaf_head; cur = cur->next) {
2075
 
                btree_node_t *node = list_get_instance(cur, btree_node_t, leaf_link);
 
2084
        
 
2085
        list_foreach(as->as_area_btree.leaf_list, cur) {
 
2086
                btree_node_t *node =
 
2087
                    list_get_instance(cur, btree_node_t, leaf_link);
2076
2088
                area_cnt += node->keys;
2077
2089
        }
2078
2090
 
2082
2094
        /* Second pass, record data. */
2083
2095
 
2084
2096
        size_t area_idx = 0;
2085
 
 
2086
 
        for (cur = as->as_area_btree.leaf_head.next; cur
2087
 
            != &as->as_area_btree.leaf_head; cur = cur->next) {
2088
 
                btree_node_t *node = list_get_instance(cur, btree_node_t, leaf_link);
 
2097
        
 
2098
        list_foreach(as->as_area_btree.leaf_list, cur) {
 
2099
                btree_node_t *node =
 
2100
                    list_get_instance(cur, btree_node_t, leaf_link);
2089
2101
                btree_key_t i;
2090
2102
 
2091
2103
                for (i = 0; i < node->keys; i++) {
2095
2107
                        mutex_lock(&area->lock);
2096
2108
 
2097
2109
                        info[area_idx].start_addr = area->base;
2098
 
                        info[area_idx].size = FRAMES2SIZE(area->pages);
 
2110
                        info[area_idx].size = P2SZ(area->pages);
2099
2111
                        info[area_idx].flags = area->flags;
2100
2112
                        ++area_idx;
2101
2113
 
2119
2131
        mutex_lock(&as->lock);
2120
2132
 
2121
2133
        /* Print out info about address space areas */
2122
 
        link_t *cur;
2123
 
        for (cur = as->as_area_btree.leaf_head.next; cur
2124
 
            != &as->as_area_btree.leaf_head; cur = cur->next) {
2125
 
                btree_node_t *node = list_get_instance(cur, btree_node_t, leaf_link);
 
2134
        list_foreach(as->as_area_btree.leaf_list, cur) {
 
2135
                btree_node_t *node
 
2136
                    = list_get_instance(cur, btree_node_t, leaf_link);
2126
2137
                btree_key_t i;
2127
2138
 
2128
2139
                for (i = 0; i < node->keys; i++) {
2130
2141
 
2131
2142
                        mutex_lock(&area->lock);
2132
2143
                        printf("as_area: %p, base=%p, pages=%zu"
2133
 
                                " (%p - %p)\n", area, (void *) area->base, area->pages,
2134
 
                            (void *) area->base, (void *) (area->base + FRAMES2SIZE(
2135
 
                                area->pages)));
 
2144
                            " (%p - %p)\n", area, (void *) area->base,
 
2145
                            area->pages, (void *) area->base,
 
2146
                            (void *) (area->base + P2SZ(area->pages)));
2136
2147
                        mutex_unlock(&area->lock);
2137
2148
                }
2138
2149
        }