Subversion Repositories HelenOS

Rev

Rev 3913 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 3913 Rev 4490
Line 416... Line 416...
416
            node =
416
            node =
417
                list_get_instance(area->used_space.leaf_head.prev,
417
                list_get_instance(area->used_space.leaf_head.prev,
418
                btree_node_t, leaf_link);
418
                btree_node_t, leaf_link);
419
            if ((cond = (bool) node->keys)) {
419
            if ((cond = (bool) node->keys)) {
420
                uintptr_t b = node->key[node->keys - 1];
420
                uintptr_t b = node->key[node->keys - 1];
421
                count_t c =
421
                size_t c =
422
                    (count_t) node->value[node->keys - 1];
422
                    (size_t) node->value[node->keys - 1];
423
                unsigned int i = 0;
423
                unsigned int i = 0;
424
           
424
           
425
                if (overlaps(b, c * PAGE_SIZE, area->base,
425
                if (overlaps(b, c * PAGE_SIZE, area->base,
426
                    pages * PAGE_SIZE)) {
426
                    pages * PAGE_SIZE)) {
427
                   
427
                   
Line 553... Line 553...
553
        unsigned int i;
553
        unsigned int i;
554
       
554
       
555
        node = list_get_instance(cur, btree_node_t, leaf_link);
555
        node = list_get_instance(cur, btree_node_t, leaf_link);
556
        for (i = 0; i < node->keys; i++) {
556
        for (i = 0; i < node->keys; i++) {
557
            uintptr_t b = node->key[i];
557
            uintptr_t b = node->key[i];
558
            count_t j;
558
            size_t j;
559
            pte_t *pte;
559
            pte_t *pte;
560
           
560
           
561
            for (j = 0; j < (count_t) node->value[i]; j++) {
561
            for (j = 0; j < (size_t) node->value[i]; j++) {
562
                page_table_lock(as, false);
562
                page_table_lock(as, false);
563
                pte = page_mapping_find(as, b + j * PAGE_SIZE);
563
                pte = page_mapping_find(as, b + j * PAGE_SIZE);
564
                ASSERT(pte && PTE_VALID(pte) &&
564
                ASSERT(pte && PTE_VALID(pte) &&
565
                    PTE_PRESENT(pte));
565
                    PTE_PRESENT(pte));
566
                if (area->backend &&
566
                if (area->backend &&
Line 786... Line 786...
786
    uintptr_t base;
786
    uintptr_t base;
787
    link_t *cur;
787
    link_t *cur;
788
    ipl_t ipl;
788
    ipl_t ipl;
789
    int page_flags;
789
    int page_flags;
790
    uintptr_t *old_frame;
790
    uintptr_t *old_frame;
791
    index_t frame_idx;
791
    size_t frame_idx;
792
    count_t used_pages;
792
    size_t used_pages;
793
   
793
   
794
    /* Flags for the new memory mapping */
794
    /* Flags for the new memory mapping */
795
    page_flags = area_flags_to_page_flags(flags);
795
    page_flags = area_flags_to_page_flags(flags);
796
 
796
 
797
    ipl = interrupts_disable();
797
    ipl = interrupts_disable();
Line 825... Line 825...
825
        btree_node_t *node;
825
        btree_node_t *node;
826
        unsigned int i;
826
        unsigned int i;
827
       
827
       
828
        node = list_get_instance(cur, btree_node_t, leaf_link);
828
        node = list_get_instance(cur, btree_node_t, leaf_link);
829
        for (i = 0; i < node->keys; i++) {
829
        for (i = 0; i < node->keys; i++) {
830
            used_pages += (count_t) node->value[i];
830
            used_pages += (size_t) node->value[i];
831
        }
831
        }
832
    }
832
    }
833
 
833
 
834
    /* An array for storing frame numbers */
834
    /* An array for storing frame numbers */
835
    old_frame = malloc(used_pages * sizeof(uintptr_t), 0);
835
    old_frame = malloc(used_pages * sizeof(uintptr_t), 0);
Line 851... Line 851...
851
        unsigned int i;
851
        unsigned int i;
852
       
852
       
853
        node = list_get_instance(cur, btree_node_t, leaf_link);
853
        node = list_get_instance(cur, btree_node_t, leaf_link);
854
        for (i = 0; i < node->keys; i++) {
854
        for (i = 0; i < node->keys; i++) {
855
            uintptr_t b = node->key[i];
855
            uintptr_t b = node->key[i];
856
            count_t j;
856
            size_t j;
857
            pte_t *pte;
857
            pte_t *pte;
858
           
858
           
859
            for (j = 0; j < (count_t) node->value[i]; j++) {
859
            for (j = 0; j < (size_t) node->value[i]; j++) {
860
                page_table_lock(as, false);
860
                page_table_lock(as, false);
861
                pte = page_mapping_find(as, b + j * PAGE_SIZE);
861
                pte = page_mapping_find(as, b + j * PAGE_SIZE);
862
                ASSERT(pte && PTE_VALID(pte) &&
862
                ASSERT(pte && PTE_VALID(pte) &&
863
                    PTE_PRESENT(pte));
863
                    PTE_PRESENT(pte));
864
                old_frame[frame_idx++] = PTE_GET_FRAME(pte);
864
                old_frame[frame_idx++] = PTE_GET_FRAME(pte);
Line 901... Line 901...
901
        unsigned int i;
901
        unsigned int i;
902
       
902
       
903
        node = list_get_instance(cur, btree_node_t, leaf_link);
903
        node = list_get_instance(cur, btree_node_t, leaf_link);
904
        for (i = 0; i < node->keys; i++) {
904
        for (i = 0; i < node->keys; i++) {
905
            uintptr_t b = node->key[i];
905
            uintptr_t b = node->key[i];
906
            count_t j;
906
            size_t j;
907
           
907
           
908
            for (j = 0; j < (count_t) node->value[i]; j++) {
908
            for (j = 0; j < (size_t) node->value[i]; j++) {
909
                page_table_lock(as, false);
909
                page_table_lock(as, false);
910
 
910
 
911
                /* Insert the new mapping */
911
                /* Insert the new mapping */
912
                page_mapping_insert(as, b + j * PAGE_SIZE,
912
                page_mapping_insert(as, b + j * PAGE_SIZE,
913
                    old_frame[frame_idx++], page_flags);
913
                    old_frame[frame_idx++], page_flags);
Line 1395... Line 1395...
1395
 * @param page      First page to be marked.
1395
 * @param page      First page to be marked.
1396
 * @param count     Number of page to be marked.
1396
 * @param count     Number of page to be marked.
1397
 *
1397
 *
1398
 * @return      Zero on failure and non-zero on success.
1398
 * @return      Zero on failure and non-zero on success.
1399
 */
1399
 */
1400
int used_space_insert(as_area_t *a, uintptr_t page, count_t count)
1400
int used_space_insert(as_area_t *a, uintptr_t page, size_t count)
1401
{
1401
{
1402
    btree_node_t *leaf, *node;
1402
    btree_node_t *leaf, *node;
1403
    count_t pages;
1403
    size_t pages;
1404
    unsigned int i;
1404
    unsigned int i;
1405
 
1405
 
1406
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
1406
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
1407
    ASSERT(count);
1407
    ASSERT(count);
1408
 
1408
 
1409
    pages = (count_t) btree_search(&a->used_space, page, &leaf);
1409
    pages = (size_t) btree_search(&a->used_space, page, &leaf);
1410
    if (pages) {
1410
    if (pages) {
1411
        /*
1411
        /*
1412
         * We hit the beginning of some used space.
1412
         * We hit the beginning of some used space.
1413
         */
1413
         */
1414
        return 0;
1414
        return 0;
Line 1421... Line 1421...
1421
 
1421
 
1422
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
1422
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
1423
    if (node) {
1423
    if (node) {
1424
        uintptr_t left_pg = node->key[node->keys - 1];
1424
        uintptr_t left_pg = node->key[node->keys - 1];
1425
        uintptr_t right_pg = leaf->key[0];
1425
        uintptr_t right_pg = leaf->key[0];
1426
        count_t left_cnt = (count_t) node->value[node->keys - 1];
1426
        size_t left_cnt = (size_t) node->value[node->keys - 1];
1427
        count_t right_cnt = (count_t) leaf->value[0];
1427
        size_t right_cnt = (size_t) leaf->value[0];
1428
       
1428
       
1429
        /*
1429
        /*
1430
         * Examine the possibility that the interval fits
1430
         * Examine the possibility that the interval fits
1431
         * somewhere between the rightmost interval of
1431
         * somewhere between the rightmost interval of
1432
         * the left neigbour and the first interval of the leaf.
1432
         * the left neigbour and the first interval of the leaf.
Line 1476... Line 1476...
1476
                leaf);
1476
                leaf);
1477
            return 1;
1477
            return 1;
1478
        }
1478
        }
1479
    } else if (page < leaf->key[0]) {
1479
    } else if (page < leaf->key[0]) {
1480
        uintptr_t right_pg = leaf->key[0];
1480
        uintptr_t right_pg = leaf->key[0];
1481
        count_t right_cnt = (count_t) leaf->value[0];
1481
        size_t right_cnt = (size_t) leaf->value[0];
1482
   
1482
   
1483
        /*
1483
        /*
1484
         * Investigate the border case in which the left neighbour does
1484
         * Investigate the border case in which the left neighbour does
1485
         * not exist but the interval fits from the left.
1485
         * not exist but the interval fits from the left.
1486
         */
1486
         */
Line 1511... Line 1511...
1511
 
1511
 
1512
    node = btree_leaf_node_right_neighbour(&a->used_space, leaf);
1512
    node = btree_leaf_node_right_neighbour(&a->used_space, leaf);
1513
    if (node) {
1513
    if (node) {
1514
        uintptr_t left_pg = leaf->key[leaf->keys - 1];
1514
        uintptr_t left_pg = leaf->key[leaf->keys - 1];
1515
        uintptr_t right_pg = node->key[0];
1515
        uintptr_t right_pg = node->key[0];
1516
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
1516
        size_t left_cnt = (size_t) leaf->value[leaf->keys - 1];
1517
        count_t right_cnt = (count_t) node->value[0];
1517
        size_t right_cnt = (size_t) node->value[0];
1518
       
1518
       
1519
        /*
1519
        /*
1520
         * Examine the possibility that the interval fits
1520
         * Examine the possibility that the interval fits
1521
         * somewhere between the leftmost interval of
1521
         * somewhere between the leftmost interval of
1522
         * the right neigbour and the last interval of the leaf.
1522
         * the right neigbour and the last interval of the leaf.
Line 1566... Line 1566...
1566
                leaf);
1566
                leaf);
1567
            return 1;
1567
            return 1;
1568
        }
1568
        }
1569
    } else if (page >= leaf->key[leaf->keys - 1]) {
1569
    } else if (page >= leaf->key[leaf->keys - 1]) {
1570
        uintptr_t left_pg = leaf->key[leaf->keys - 1];
1570
        uintptr_t left_pg = leaf->key[leaf->keys - 1];
1571
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
1571
        size_t left_cnt = (size_t) leaf->value[leaf->keys - 1];
1572
   
1572
   
1573
        /*
1573
        /*
1574
         * Investigate the border case in which the right neighbour
1574
         * Investigate the border case in which the right neighbour
1575
         * does not exist but the interval fits from the right.
1575
         * does not exist but the interval fits from the right.
1576
         */
1576
         */
Line 1604... Line 1604...
1604
     */
1604
     */
1605
    for (i = 1; i < leaf->keys; i++) {
1605
    for (i = 1; i < leaf->keys; i++) {
1606
        if (page < leaf->key[i]) {
1606
        if (page < leaf->key[i]) {
1607
            uintptr_t left_pg = leaf->key[i - 1];
1607
            uintptr_t left_pg = leaf->key[i - 1];
1608
            uintptr_t right_pg = leaf->key[i];
1608
            uintptr_t right_pg = leaf->key[i];
1609
            count_t left_cnt = (count_t) leaf->value[i - 1];
1609
            size_t left_cnt = (size_t) leaf->value[i - 1];
1610
            count_t right_cnt = (count_t) leaf->value[i];
1610
            size_t right_cnt = (size_t) leaf->value[i];
1611
 
1611
 
1612
            /*
1612
            /*
1613
             * The interval fits between left_pg and right_pg.
1613
             * The interval fits between left_pg and right_pg.
1614
             */
1614
             */
1615
 
1615
 
Line 1663... Line 1663...
1663
                return 1;
1663
                return 1;
1664
            }
1664
            }
1665
        }
1665
        }
1666
    }
1666
    }
1667
 
1667
 
1668
    panic("Inconsistency detected while adding %" PRIc " pages of used "
1668
    panic("Inconsistency detected while adding %" PRIs " pages of used "
1669
        "space at %p.", count, page);
1669
        "space at %p.", count, page);
1670
}
1670
}
1671
 
1671
 
1672
/** Mark portion of address space area as unused.
1672
/** Mark portion of address space area as unused.
1673
 *
1673
 *
Line 1677... Line 1677...
1677
 * @param page      First page to be marked.
1677
 * @param page      First page to be marked.
1678
 * @param count     Number of page to be marked.
1678
 * @param count     Number of page to be marked.
1679
 *
1679
 *
1680
 * @return      Zero on failure and non-zero on success.
1680
 * @return      Zero on failure and non-zero on success.
1681
 */
1681
 */
1682
int used_space_remove(as_area_t *a, uintptr_t page, count_t count)
1682
int used_space_remove(as_area_t *a, uintptr_t page, size_t count)
1683
{
1683
{
1684
    btree_node_t *leaf, *node;
1684
    btree_node_t *leaf, *node;
1685
    count_t pages;
1685
    size_t pages;
1686
    unsigned int i;
1686
    unsigned int i;
1687
 
1687
 
1688
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
1688
    ASSERT(page == ALIGN_DOWN(page, PAGE_SIZE));
1689
    ASSERT(count);
1689
    ASSERT(count);
1690
 
1690
 
1691
    pages = (count_t) btree_search(&a->used_space, page, &leaf);
1691
    pages = (size_t) btree_search(&a->used_space, page, &leaf);
1692
    if (pages) {
1692
    if (pages) {
1693
        /*
1693
        /*
1694
         * We are lucky, page is the beginning of some interval.
1694
         * We are lucky, page is the beginning of some interval.
1695
         */
1695
         */
1696
        if (count > pages) {
1696
        if (count > pages) {
Line 1715... Line 1715...
1715
    }
1715
    }
1716
 
1716
 
1717
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
1717
    node = btree_leaf_node_left_neighbour(&a->used_space, leaf);
1718
    if (node && page < leaf->key[0]) {
1718
    if (node && page < leaf->key[0]) {
1719
        uintptr_t left_pg = node->key[node->keys - 1];
1719
        uintptr_t left_pg = node->key[node->keys - 1];
1720
        count_t left_cnt = (count_t) node->value[node->keys - 1];
1720
        size_t left_cnt = (size_t) node->value[node->keys - 1];
1721
 
1721
 
1722
        if (overlaps(left_pg, left_cnt * PAGE_SIZE, page,
1722
        if (overlaps(left_pg, left_cnt * PAGE_SIZE, page,
1723
            count * PAGE_SIZE)) {
1723
            count * PAGE_SIZE)) {
1724
            if (page + count * PAGE_SIZE ==
1724
            if (page + count * PAGE_SIZE ==
1725
                left_pg + left_cnt * PAGE_SIZE) {
1725
                left_pg + left_cnt * PAGE_SIZE) {
Line 1731... Line 1731...
1731
                 */
1731
                 */
1732
                node->value[node->keys - 1] -= count;
1732
                node->value[node->keys - 1] -= count;
1733
                return 1;
1733
                return 1;
1734
            } else if (page + count * PAGE_SIZE <
1734
            } else if (page + count * PAGE_SIZE <
1735
                left_pg + left_cnt*PAGE_SIZE) {
1735
                left_pg + left_cnt*PAGE_SIZE) {
1736
                count_t new_cnt;
1736
                size_t new_cnt;
1737
               
1737
               
1738
                /*
1738
                /*
1739
                 * The interval is contained in the rightmost
1739
                 * The interval is contained in the rightmost
1740
                 * interval of the left neighbour but its
1740
                 * interval of the left neighbour but its
1741
                 * removal requires both updating the size of
1741
                 * removal requires both updating the size of
Line 1755... Line 1755...
1755
        return 0;
1755
        return 0;
1756
    }
1756
    }
1757
   
1757
   
1758
    if (page > leaf->key[leaf->keys - 1]) {
1758
    if (page > leaf->key[leaf->keys - 1]) {
1759
        uintptr_t left_pg = leaf->key[leaf->keys - 1];
1759
        uintptr_t left_pg = leaf->key[leaf->keys - 1];
1760
        count_t left_cnt = (count_t) leaf->value[leaf->keys - 1];
1760
        size_t left_cnt = (size_t) leaf->value[leaf->keys - 1];
1761
 
1761
 
1762
        if (overlaps(left_pg, left_cnt * PAGE_SIZE, page,
1762
        if (overlaps(left_pg, left_cnt * PAGE_SIZE, page,
1763
            count * PAGE_SIZE)) {
1763
            count * PAGE_SIZE)) {
1764
            if (page + count * PAGE_SIZE ==
1764
            if (page + count * PAGE_SIZE ==
1765
                left_pg + left_cnt * PAGE_SIZE) {
1765
                left_pg + left_cnt * PAGE_SIZE) {
Line 1770... Line 1770...
1770
                 */
1770
                 */
1771
                leaf->value[leaf->keys - 1] -= count;
1771
                leaf->value[leaf->keys - 1] -= count;
1772
                return 1;
1772
                return 1;
1773
            } else if (page + count * PAGE_SIZE < left_pg +
1773
            } else if (page + count * PAGE_SIZE < left_pg +
1774
                left_cnt * PAGE_SIZE) {
1774
                left_cnt * PAGE_SIZE) {
1775
                count_t new_cnt;
1775
                size_t new_cnt;
1776
               
1776
               
1777
                /*
1777
                /*
1778
                 * The interval is contained in the rightmost
1778
                 * The interval is contained in the rightmost
1779
                 * interval of the leaf but its removal
1779
                 * interval of the leaf but its removal
1780
                 * requires both updating the size of the
1780
                 * requires both updating the size of the
Line 1797... Line 1797...
1797
     * Now the interval can be only between intervals of the leaf.
1797
     * Now the interval can be only between intervals of the leaf.
1798
     */
1798
     */
1799
    for (i = 1; i < leaf->keys - 1; i++) {
1799
    for (i = 1; i < leaf->keys - 1; i++) {
1800
        if (page < leaf->key[i]) {
1800
        if (page < leaf->key[i]) {
1801
            uintptr_t left_pg = leaf->key[i - 1];
1801
            uintptr_t left_pg = leaf->key[i - 1];
1802
            count_t left_cnt = (count_t) leaf->value[i - 1];
1802
            size_t left_cnt = (size_t) leaf->value[i - 1];
1803
 
1803
 
1804
            /*
1804
            /*
1805
             * Now the interval is between intervals corresponding
1805
             * Now the interval is between intervals corresponding
1806
             * to (i - 1) and i.
1806
             * to (i - 1) and i.
1807
             */
1807
             */
Line 1817... Line 1817...
1817
                     */
1817
                     */
1818
                    leaf->value[i - 1] -= count;
1818
                    leaf->value[i - 1] -= count;
1819
                    return 1;
1819
                    return 1;
1820
                } else if (page + count * PAGE_SIZE <
1820
                } else if (page + count * PAGE_SIZE <
1821
                    left_pg + left_cnt * PAGE_SIZE) {
1821
                    left_pg + left_cnt * PAGE_SIZE) {
1822
                    count_t new_cnt;
1822
                    size_t new_cnt;
1823
               
1823
               
1824
                    /*
1824
                    /*
1825
                     * The interval is contained in the
1825
                     * The interval is contained in the
1826
                     * interval (i - 1) of the leaf but its
1826
                     * interval (i - 1) of the leaf but its
1827
                     * removal requires both updating the
1827
                     * removal requires both updating the
Line 1842... Line 1842...
1842
            return 0;
1842
            return 0;
1843
        }
1843
        }
1844
    }
1844
    }
1845
 
1845
 
1846
error:
1846
error:
1847
    panic("Inconsistency detected while removing %" PRIc " pages of used "
1847
    panic("Inconsistency detected while removing %" PRIs " pages of used "
1848
        "space from %p.", count, page);
1848
        "space from %p.", count, page);
1849
}
1849
}
1850
 
1850
 
1851
/** Remove reference to address space area share info.
1851
/** Remove reference to address space area share info.
1852
 *
1852
 *
Line 1941... Line 1941...
1941
        unsigned int i;
1941
        unsigned int i;
1942
        for (i = 0; i < node->keys; i++) {
1942
        for (i = 0; i < node->keys; i++) {
1943
            as_area_t *area = node->value[i];
1943
            as_area_t *area = node->value[i];
1944
       
1944
       
1945
            mutex_lock(&area->lock);
1945
            mutex_lock(&area->lock);
1946
            printf("as_area: %p, base=%p, pages=%" PRIc
1946
            printf("as_area: %p, base=%p, pages=%" PRIs
1947
                " (%p - %p)\n", area, area->base, area->pages,
1947
                " (%p - %p)\n", area, area->base, area->pages,
1948
                area->base, area->base + FRAMES2SIZE(area->pages));
1948
                area->base, area->base + FRAMES2SIZE(area->pages));
1949
            mutex_unlock(&area->lock);
1949
            mutex_unlock(&area->lock);
1950
        }
1950
        }
1951
    }
1951
    }