lkml.org 
[lkml]   [2003]   [Nov]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    SubjectRe: hash table sizes
    Date
    Hi Jens,

    I was wondering about you funny formula, too. (especially because it was 23 -
    (PAGE_SHIFT -1) and not 24 - PAGE_SHIFT ;-) So I wanted to find out why this:
    1: mempages >>= (23 - (PAGE_SHIFT - 1));
    2: order = max(2, fls(mempages));
    3: order = min(12, order);

    should be similar to this original code:
    4: mempages >>= (14 - PAGE_SHIFT);
    5: mempages *= sizeof(struct hlist_head);
    6: for (order = 0; ((1UL << order) << PAGE_SHIFT) < mempages; order++)
    7: ;

    Well, first I saw that lines 2 and 3 make order to be between 2 and 12. OK
    this is new, and I like it ;-) Then I saw you tried to convert the ugly lines
    6 + 7 into a fls() call. Fine! (I like that, too) Line 6 + 7 can be converted
    to following (almost equivalent) lines:
    6 + 7 -> 8a: order = fls(mempages) - PAGE_SHIFT;
    or
    6 + 7 -> 8b: order = fls(mempages >> PAGE_SHIFT);

    Now the shift is not present in line 2, so I folded it from line 8b into line
    4 and got:
    4 -> 9: mempages >>= 14;
    5: mempages *= sizeof(struct hlist_head);
    8b -> 10: order = fls(mempages);

    But to make the math a bit more correct the multiplication from line 5 has to
    be done before the shift in line 9. So I got following simple two lines
    equivalent to lines 4 to 7:
    5 + 9 -> 11: mempages = (mempages * sizeof(struct hlist_head)) >> 14;
    10: order = fls(mempages);

    So, now we can compare line 1 and 11. OK, let's assume PAGE_SHIFT = 12. So we
    get:
    1 -> 12: mempages >>= (23 - (12 - 1)); // right shift by 12

    If sizeof(struct hlist_head) == 4, we get for line 10:
    11 -> 13: mempages = (mempages * 4) >> 14; // right shift by 12

    And HURRAY, we've got it...!
    But they are only equivalent if (PAGE_SHIFT == 12) && (sizeof(struct
    hlist_head) == 4)...

    So I propose the attached patch which should be closer to the original and
    makes order not to be greater than 12. (Btw. this only changes anything for
    more than 2^24 pages of memory, so I think this is a good idea!)

    Best reagrds
    Thomas Schlichter

    On Tuesday 25 November 2003 14:54, Jes Sorensen wrote:
    > >>>>> "William" == William Lee Irwin <wli@holomorphy.com> writes:
    >
    > William> On Tue, Nov 25, 2003 at 08:35:49AM -0500, Jes Sorensen wrote:
    > >> + mempages >>= (23 - (PAGE_SHIFT - 1)); + order = max(2,
    > >> fls(mempages)); + order = min(12, order);
    >
    > William> This is curious; what's 23 - (PAGE_SHIFT - 1) supposed to
    > William> represent?
    >
    > Well MB >> 2 or consider it trial and error ;-)
    >
    > Cheers,
    > Jes
    --- linux-2.6.0-test9-mm5/fs/dcache.c.orig Tue Nov 25 15:29:38 2003
    +++ linux-2.6.0-test9-mm5/fs/dcache.c Tue Nov 25 16:18:37 2003
    @@ -1530,9 +1530,8 @@
    static void __init dcache_init(unsigned long mempages)
    {
    struct hlist_head *d;
    - unsigned long order;
    unsigned int nr_hash;
    - int i;
    + int i, order;

    /*
    * A constructor could be added for stable state like the lists,
    @@ -1552,12 +1551,10 @@

    set_shrinker(DEFAULT_SEEKS, shrink_dcache_memory);

    -#if PAGE_SHIFT < 13
    - mempages >>= (13 - PAGE_SHIFT);
    -#endif
    - mempages *= sizeof(struct hlist_head);
    - for (order = 0; ((1UL << order) << PAGE_SHIFT) < mempages; order++)
    - ;
    + mempages = (mempages * sizeof(struct hlist_head)) >> 13;
    + order = fls(mempages);
    + if (order > 12)
    + order = 12;

    do {
    unsigned long tmp;
    @@ -1575,7 +1572,7 @@
    __get_free_pages(GFP_ATOMIC, order);
    } while (dentry_hashtable == NULL && --order >= 0);

    - printk(KERN_INFO "Dentry cache hash table entries: %d (order: %ld, %ld bytes)\n",
    + printk(KERN_INFO "Dentry cache hash table entries: %d (order: %d, %ld bytes)\n",
    nr_hash, order, (PAGE_SIZE << order));

    if (!dentry_hashtable)
    --- linux-2.6.0-test9-mm5/fs/inode.c.orig Tue Nov 25 15:33:22 2003
    +++ linux-2.6.0-test9-mm5/fs/inode.c Tue Nov 25 16:17:38 2003
    @@ -1319,17 +1319,16 @@
    void __init inode_init(unsigned long mempages)
    {
    struct hlist_head *head;
    - unsigned long order;
    unsigned int nr_hash;
    - int i;
    + int i, order;

    for (i = 0; i < ARRAY_SIZE(i_wait_queue_heads); i++)
    init_waitqueue_head(&i_wait_queue_heads[i].wqh);

    - mempages >>= (14 - PAGE_SHIFT);
    - mempages *= sizeof(struct hlist_head);
    - for (order = 0; ((1UL << order) << PAGE_SHIFT) < mempages; order++)
    - ;
    + mempages = (mempages * sizeof(struct hlist_head)) >> 14;
    + order = fls(mempages);
    + if (order > 12)
    + order = 12;

    do {
    unsigned long tmp;
    @@ -1347,7 +1346,7 @@
    __get_free_pages(GFP_ATOMIC, order);
    } while (inode_hashtable == NULL && --order >= 0);

    - printk("Inode-cache hash table entries: %d (order: %ld, %ld bytes)\n",
    + printk("Inode-cache hash table entries: %d (order: %d, %ld bytes)\n",
    nr_hash, order, (PAGE_SIZE << order));

    if (!inode_hashtable)[unhandled content-type:application/pgp-signature]
    \
     
     \ /
      Last update: 2005-03-22 13:58    [W:0.064 / U:0.060 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site