pagemap.c 6.25 KB
Newer Older
1 2 3 4 5 6 7 8 9
/* Wendelin.bigfile | Pgoffset -> page mapping
 * Copyright (C) 2014-2015  Nexedi SA and Contributors.
 *                          Kirill Smelkov <kirr@nexedi.com>
 *
 * This program is free software: you can Use, Study, Modify and Redistribute
 * it under the terms of the GNU General Public License version 3, or (at your
 * option) any later version, as published by the Free Software Foundation.
 *
 * You can also Link and Combine this program with other software covered by
10 11 12 13
 * the terms of any of the Free Software licenses or any of the Open Source
 * Initiative approved licenses and Convey the resulting work. Corresponding
 * source of such a combination shall include the source code for all other
 * software used.
14 15 16 17 18
 *
 * This program is distributed WITHOUT ANY WARRANTY; without even the implied
 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * See COPYING file for full licensing terms.
19
 * See https://www.nexedi.com/licensing for rationale and options.
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235
 *
 * ~~~~~~~~
 *
 * Implementation of get/set/del/clear for PageMap.
 * See wendelin/bigfile/pagemap.h for general PageMap description.
 */

#include <wendelin/bigfile/pagemap.h>
#include <wendelin/bug.h>

#include <sys/mman.h>


/* allocate 1 hw page from OS */
static void *os_alloc_page(void)
{
    // -> xmmap ?
    void *addr;
    addr = mmap(NULL, PAGE_SIZE, PROT_READ | PROT_WRITE,
                MAP_PRIVATE | MAP_ANONYMOUS /* | MAP_POPULATE */,
                -1, 0);
    if (addr == MAP_FAILED)
        addr = NULL;

    return addr;
}

static void *os_xalloc_page(void)
{
    void *addr = os_alloc_page();
    if(!addr)
        BUGe();
    return addr;
}

/* deallocate 1 hw page to OS */
static void os_free_page(void *addr)
{
    /* must not fail */
    xmunmap(addr, PAGE_SIZE);
}





void pagemap_init(PageMap *pmap, unsigned pageshift)
{
    unsigned height;

    height = (8*sizeof(pgoff_t) - pageshift + (PAGEMAP_LEVEL_BITS - 1)) /
                PAGEMAP_LEVEL_BITS;

    pmap->pmap0 = 0ULL;
    pmap->rshift0 = height * PAGEMAP_LEVEL_BITS;
}


Page *pagemap_get(const PageMap *pmap, pgoff_t pgoffset)
{
    unsigned rshift = pmap->rshift0;
    void ***tail, **tab;
    unsigned idx;

    BUG_ON(pgoffset >> rshift);

    /* walk through tables
     *
     * tail - points to entry in previous-level table,
     * tab  - to current-level table,
     * idx  - index of entry in current table
     *
     *                    tab
     *           +-----+    ,+-----+
     *           |     |   | |     |
     *      tail +-----+---  |     |
     *           +-----+     |     |    -> ...
     *           |     |     |     |   |
     *           |     | idx +-----+---
     *           +-----+     +-----+
     */
    tail = (void ***)&pmap->pmap0;
    while (1) {
        rshift -= PAGEMAP_LEVEL_BITS;
        idx = (pgoffset >> rshift) & PAGEMAP_NR_MASK;

        tab = *tail;
        if (!tab)
            return NULL;    /* table not present - not found */

        tab = PTR_POINTER(tab);

        if (!rshift)
            break;

        // XXX move up?
        tail = (void ***)&tab[idx];
    }

    /* final-level table found - get result from there */
    return tab[idx];
}


void pagemap_set(PageMap *pmap, pgoff_t pgoffset, Page *page)
{
    unsigned rshift = pmap->rshift0;
    void ***tail, **tab;
    unsigned idx;

    BUG_ON(pgoffset >> rshift);
    BUG_ON(!page);   // XXX or better call pagemap_del() ?

    /* walk through tables, allocating memory along the way, if needed
     * (see who is who in pagemap_get) */
    tail = (void ***)&pmap->pmap0;
    while(1) {
        rshift -= PAGEMAP_LEVEL_BITS;
        idx = (pgoffset >> rshift) & PAGEMAP_NR_MASK;

        tab = *tail;
        if (!tab) {
            tab = os_xalloc_page(); /* NOTE - is hw page aligned */
            BUG_ON(tab != PTR_POINTER(tab));
            /* NOTE for newly allocated tab we don't need to adjust count for
             *      *tail - xcount=0 means there is 1 entry (which we'll set) */
            *tail = tab;
        }
        else {
            tab = PTR_POINTER(tab);

            /* entry empty - adjust tail counter as we'll next either be setting
             * new table pointer, or page pointer to it */
            if (!tab[idx])
                *tail = PTR_XCOUNT_ADD(*tail, +1);
        }

        if (!rshift)
            break;

        // XXX move up?
        tail = (void ***)&tab[idx];
    }

    tab[idx] = page;
}


int pagemap_del(PageMap *pmap, pgoff_t pgoffset)
{
    unsigned rshift = pmap->rshift0;
    unsigned height = rshift / PAGEMAP_LEVEL_BITS;
    unsigned idx, l /* current level */;
    /* tailv[l] points to tail pointing to entry pointing to tab_i */
    void ***tailv[height], **tab;   // XXX height -> height+1 ?

    BUG_ON(pgoffset >> rshift);

    /* walk tables to the end and see if entry is there
     * (see who is who in pagemap_get) */
    l = 0;
    tailv[0] = (void ***)&pmap->pmap0;
    while (1) {
        rshift -= PAGEMAP_LEVEL_BITS;
        idx = (pgoffset >> rshift) & PAGEMAP_NR_MASK;

        tab = *tailv[l];
        if (!tab)
            return 0;   /* entry already missing */
        tab = PTR_POINTER(tab);

        if (!rshift)
            break;

        tailv[++l] = (void ***)&tab[idx];
    }

    if (!tab[idx])
        return 0;   /* not found in last-level */

    /* entry present - clear it and unwind back, decreasing counters and
     * freeing tables memory along the way */
    tab[idx] = NULL;
    do {
        void ***tail = tailv[l];

        if (PTR_XCOUNT(*tail)) {
            *tail = PTR_XCOUNT_ADD(*tail, -1);
            break;  /* other entries present - nothing to delete */
        }

        /* table became empty - free & forget it */
        os_free_page(*tail);
        *tail = NULL;
    } while (l--);

    return 1;
}


void pagemap_clear(PageMap *pmap)
{
    /* leverage pagemap walker logic, but nothing to do with leaf table
     * contents - the freeing is done when going each level up */
    __pagemap_for_each_leaftab(tab, tailv, l, pmap,
            /* when going level up: */
            {
                os_free_page(PTR_POINTER(*tailv[l]));

                /* clearing not needed - we'll free this memory at next step
                 * anyway, but easier for debugging for now */
                *tailv[l] = NULL;
            }
        )
            (void)tab; /* unused */
}