lkml.org 
[lkml]   [2003]   [Apr]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    SubjectRe: [RFC] first try for swap prefetch
    Thomas Schlichter <schlicht@uni-mannheim.de> wrote:
    >
    > > you can just do
    > >
    > > if (radix_tree_delete(...) != -ENOENT)
    > > list_del(...)
    > >
    > > + read_swap_cache_async(entry);
    >
    > Sorry, but I think I can not. The list_del() needs the value returned by
    > radix_tree_lookup(), so I can not kick it...

    OK, I'll change radix_tree_delete() to return the deleted object address if
    it was found, else NULL. That's a better API.

    > Do you know how expensive the radix_tree_lookup() is? O(1) or O(log(n))?? For
    > my shame I do not really know that data structure... :-(

    It is proportional to

    log_base_64(largest index which the tree has ever stored)

    log_base_64: because each node has 64 slots. Each time maxindex grows by a
    factor of 64 we need to introduce a new level.

    "largest index ever": because we do not (and cannot feasibly) reduce the
    height when items are removed.

    > > It might make sense to poke the speculative swapin code in the page-freeing
    > > path too.
    >
    > I wanted to do this but don't know which function is the correct one for this.
    > But I will search harder... or can you give me a hint?

    free_pages_bulk() would probably suit.



    diff -puN fs/nfs/write.c~radix_tree_delete-api-cleanup fs/nfs/write.c
    diff -puN lib/radix-tree.c~radix_tree_delete-api-cleanup lib/radix-tree.c
    --- 25/lib/radix-tree.c~radix_tree_delete-api-cleanup Fri Apr 11 14:30:30 2003
    +++ 25-akpm/lib/radix-tree.c Fri Apr 11 14:30:30 2003
    @@ -349,15 +349,18 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
    * @index: index key
    *
    * Remove the item at @index from the radix tree rooted at @root.
    + *
    + * Returns the address of the deleted item, or NULL if it was not present.
    */
    -int radix_tree_delete(struct radix_tree_root *root, unsigned long index)
    +void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
    {
    struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
    unsigned int height, shift;
    + void *ret = NULL;

    height = root->height;
    if (index > radix_tree_maxindex(height))
    - return -ENOENT;
    + goto out;

    shift = (height-1) * RADIX_TREE_MAP_SHIFT;
    pathp->node = NULL;
    @@ -365,7 +368,7 @@ int radix_tree_delete(struct radix_tree_

    while (height > 0) {
    if (*pathp->slot == NULL)
    - return -ENOENT;
    + goto out;

    pathp[1].node = *pathp[0].slot;
    pathp[1].slot = (struct radix_tree_node **)
    @@ -375,8 +378,9 @@ int radix_tree_delete(struct radix_tree_
    height--;
    }

    - if (*pathp[0].slot == NULL)
    - return -ENOENT;
    + ret = *pathp[0].slot;
    + if (ret == NULL)
    + goto out;

    *pathp[0].slot = NULL;
    while (pathp[0].node && --pathp[0].node->count == 0) {
    @@ -387,8 +391,8 @@ int radix_tree_delete(struct radix_tree_

    if (root->rnode == NULL)
    root->height = 0; /* Empty tree, we can reset the height */
    -
    - return 0;
    +out:
    + return ret;
    }
    EXPORT_SYMBOL(radix_tree_delete);

    diff -puN mm/filemap.c~radix_tree_delete-api-cleanup mm/filemap.c
    diff -puN include/linux/radix-tree.h~radix_tree_delete-api-cleanup include/linux/radix-tree.h
    --- 25/include/linux/radix-tree.h~radix_tree_delete-api-cleanup Fri Apr 11 14:30:30 2003
    +++ 25-akpm/include/linux/radix-tree.h Fri Apr 11 14:30:30 2003
    @@ -43,7 +43,7 @@ do { \

    extern int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
    extern void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
    -extern int radix_tree_delete(struct radix_tree_root *, unsigned long);
    +extern void *radix_tree_delete(struct radix_tree_root *, unsigned long);
    extern unsigned int
    radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
    unsigned long first_index, unsigned int max_items);
    _

    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 13:34    [W:0.026 / U:1.284 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site