[bug report] maple_tree: make mas_validate_gaps() to check metadata

Dan Carpenter dan.carpenter at linaro.org
Thu Nov 9 02:06:46 PST 2023


Hello Peng Zhang,

The patch f8e5eac8abe3: "maple_tree: make mas_validate_gaps() to
check metadata" from Jul 11, 2023 (linux-next), leads to the
following Smatch static checker warning:

	lib/maple_tree.c:7258 mas_validate_gaps()
	error: we previously assumed 'gaps' could be null (see line 7225)

lib/maple_tree.c
    7196 static void mas_validate_gaps(struct ma_state *mas)
    7197 {
    7198         struct maple_enode *mte = mas->node;
    7199         struct maple_node *p_mn, *node = mte_to_node(mte);
    7200         enum maple_type mt = mte_node_type(mas->node);
    7201         unsigned long gap = 0, max_gap = 0;
    7202         unsigned long p_end, p_start = mas->min;
    7203         unsigned char p_slot, offset;
    7204         unsigned long *gaps = NULL;
    7205         unsigned long *pivots = ma_pivots(node, mt);
    7206         unsigned int i;
    7207 
    7208         if (ma_is_dense(mt)) {
    7209                 for (i = 0; i < mt_slot_count(mte); i++) {
    7210                         if (mas_get_slot(mas, i)) {
    7211                                 if (gap > max_gap)
    7212                                         max_gap = gap;
    7213                                 gap = 0;
    7214                                 continue;
    7215                         }
    7216                         gap++;
    7217                 }
    7218                 goto counted;
    7219         }
    7220 
    7221         gaps = ma_gaps(node, mt);
    7222         for (i = 0; i < mt_slot_count(mte); i++) {
    7223                 p_end = mas_safe_pivot(mas, pivots, i, mt);
    7224 
    7225                 if (!gaps) {
                             ^^^^^
Check for NULL

    7226                         if (!mas_get_slot(mas, i))
    7227                                 gap = p_end - p_start + 1;
    7228                 } else {
    7229                         void *entry = mas_get_slot(mas, i);
    7230 
    7231                         gap = gaps[i];

Re-assigned here but only if it's non-NULL to begin with.

    7232                         MT_BUG_ON(mas->tree, !entry);
    7233 
    7234                         if (gap > p_end - p_start + 1) {
    7235                                 pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n",
    7236                                        mas_mn(mas), i, gap, p_end, p_start,
    7237                                        p_end - p_start + 1);
    7238                                 MT_BUG_ON(mas->tree, gap > p_end - p_start + 1);
    7239                         }
    7240                 }
    7241 
    7242                 if (gap > max_gap)
    7243                         max_gap = gap;
    7244 
    7245                 p_start = p_end + 1;
    7246                 if (p_end >= mas->max)
    7247                         break;
    7248         }
    7249 
    7250 counted:
    7251         if (mt == maple_arange_64) {

Presumably this means that ma_gaps() can't return NULL...

    7252                 offset = ma_meta_gap(node, mt);
    7253                 if (offset > i) {
    7254                         pr_err("gap offset %p[%u] is invalid\n", node, offset);
    7255                         MT_BUG_ON(mas->tree, 1);
    7256                 }
    7257 
--> 7258                 if (gaps[offset] != max_gap) {
                             ^^^^
Unchecked dereference

    7259                         pr_err("gap %p[%u] is not the largest gap %lu\n",
    7260                                node, offset, max_gap);
    7261                         MT_BUG_ON(mas->tree, 1);
    7262                 }
    7263 
    7264                 MT_BUG_ON(mas->tree, !gaps);
                                              ^^^^^
Already crashed at this point.

    7265                 for (i++ ; i < mt_slot_count(mte); i++) {
    7266                         if (gaps[i] != 0) {
    7267                                 pr_err("gap %p[%u] beyond node limit != 0\n",
    7268                                        node, i);
    7269                                 MT_BUG_ON(mas->tree, 1);
    7270                         }
    7271                 }
    7272         }
    7273 
    7274         if (mte_is_root(mte))
    7275                 return;
    7276 
    7277         p_slot = mte_parent_slot(mas->node);
    7278         p_mn = mte_parent(mte);
    7279         MT_BUG_ON(mas->tree, max_gap > mas->max);
    7280         if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) {
    7281                 pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap);
    7282                 mt_dump(mas->tree, mt_dump_hex);
    7283                 MT_BUG_ON(mas->tree, 1);
    7284         }
    7285 }

regards,
dan carpenter



More information about the maple-tree mailing list