Potential bug in nova_find_free_slot?

[Icarusradio]

In nova_find_free_slot, I think this part of the code might have a potential bug

if (!ret_node) {
    *prev = *next = NULL;
} else if (ret_node->range_high < range_low) {
    *prev = ret_node;
    tmp = rb_next(&ret_node->node);
    if (tmp) {
        *next = container_of(tmp, struct nova_range_node, node);
        check_next = 1;
    } else {
        *next = NULL;
    }
} else if (ret_node->range_low > range_high) {
    *next = ret_node;
    tmp = rb_prev(&ret_node->node);
    if (tmp) {
        *prev = container_of(tmp, struct nova_range_node, node);
        check_prev = 1;
    } else {
        *prev = NULL;
    }
} else {
    nova_dbg("%s ERROR: %lu - %lu overlaps with existing "
         "node %lu - %lu\n",
         __func__, range_low, range_high, ret_node->range_low,
        ret_node->range_high);
    return -EINVAL;
}

The problem exists in the second branch: it is possible that ret_node->range_high < range_low and tmp->range_low < range_high. Because when nova_find_range_node(tree, range_low, NODE_BLOCK, &ret_node) returns 0 and ret_node != NULL, it only guarantees that there is no node that node->range_low <= range_low <= node->range_high, it promises nothing about range_high. So it is possible that tmp->range_low < range_high and thus leads to an overlap.

[Andiry]

That is not gonna happen. nova_find_free_slot is used in nova_free_blocks, meaning [range_low, range_high] has been allocated and not in the rb tree. So it is impossible that tmp->range_low < range_high, which implies the range we have allocated are still available in the free space tree.

Thanks, Andiry

On Thu, Aug 26, 2021 at 8:52 AM Icarus Radio @.***> wrote:

In nova_find_free_slot, I think this part of the code might have a potential bug

if (!ret_node) { prev = next = NULL; } else if (ret_node->range_high < range_low) { prev = ret_node; tmp = rb_next(&ret_node->node); if (tmp) { next = container_of(tmp, struct nova_range_node, node); check_next = 1; } else { next = NULL; } } else if (ret_node->range_low > range_high) { next = ret_node; tmp = rb_prev(&ret_node->node); if (tmp) { prev = container_of(tmp, struct nova_range_node, node); check_prev = 1; } else { prev = NULL; } } else { nova_dbg("%s ERROR: %lu - %lu overlaps with existing " "node %lu - %lu\n", func, range_low, range_high, ret_node->range_low, ret_node->range_high); return -EINVAL; }

The problem exists in the second branch: it is possible that ret_node->range_high < range_low and tmp->range_low < range_high. Because when nova_find_range_node(tree, range_low, NODE_BLOCK, &ret_node) returns 0 and ret_node != NULL, it only guarantees that there is no node that node->range_low <= range_low <= node->range_high, it promises nothing about range_high. So it is possible that tmp->range_low < range_high and thus leads to an overlap.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_NVSL_linux-2Dnova_issues_112&d=DwMCaQ&c=-35OiAkTchMrZOngvJPOeA&r=HMwrvpNIfGkJhfYgtfzIcE0EiyctTLdPd2f9rzvJviU&m=soALliUZm7_m0jtBWV3GyisK9ZeMjnkAKwA0ARa26SM&s=UOv5hSVhvtzmfxpzsoC1uYLswSjNJR8ATBaUZgAEnfU&e=, or unsubscribe https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_notifications_unsubscribe-2Dauth_AAKBYEAB65KE3KJA2DSPBATT6ZPLXANCNFSM5C3VHYTQ&d=DwMCaQ&c=-35OiAkTchMrZOngvJPOeA&r=HMwrvpNIfGkJhfYgtfzIcE0EiyctTLdPd2f9rzvJviU&m=soALliUZm7_m0jtBWV3GyisK9ZeMjnkAKwA0ARa26SM&s=7Oqce65_wQ0RbojVCZGN5HGl4h831jo9Y0pxujl-G2g&e= . Triage notifications on the go with GitHub Mobile for iOS https://urldefense.proofpoint.com/v2/url?u=https-3A__apps.apple.com_app_apple-2Dstore_id1477376905-3Fct-3Dnotification-2Demail-26mt-3D8-26pt-3D524675&d=DwMCaQ&c=-35OiAkTchMrZOngvJPOeA&r=HMwrvpNIfGkJhfYgtfzIcE0EiyctTLdPd2f9rzvJviU&m=soALliUZm7_m0jtBWV3GyisK9ZeMjnkAKwA0ARa26SM&s=DcjePmo3xQkVqqqgyRsUSKLdqGwtWvXcCHT2vIcq0U8&e= or Android https://urldefense.proofpoint.com/v2/url?u=https-3A__play.google.com_store_apps_details-3Fid-3Dcom.github.android-26utm-5Fcampaign-3Dnotification-2Demail&d=DwMCaQ&c=-35OiAkTchMrZOngvJPOeA&r=HMwrvpNIfGkJhfYgtfzIcE0EiyctTLdPd2f9rzvJviU&m=soALliUZm7_m0jtBWV3GyisK9ZeMjnkAKwA0ARa26SM&s=nAOKZ-9tiBzZP3a--tBfKlGKynxWEGZGq0YcsVrq2Yc&e= .

[Icarusradio]

Okay, I will close this issue.