ras: fix an off-by-one error in __find_elem()

ce_arr.array[] is always within the range [0, ce_arr.n-1]. However, the binary search code in __find_elem() uses ce_arr.n as the maximum index, which could lead to an off-by-one out-of-bound access when the element after the last is exactly the one just got deleted, that is, 'min' returned to caller as 'ce_arr.n'.

---
 drivers/ras/cec.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 2d9ec378a8bc..61332c9aab5a 100644
@@ -184,7 +184,7 @@ static void cec_timer_fn(struct timer_list *unused)
 static int __find_elem(struct ce_array *ca, u64 pfn, unsigned int *to)
 {
 	u64 this_pfn;
-	int min = 0, max = ca->n;
+	int min = 0, max = ca->n - 1;
 
 	while (min < max) {
 		int tmp = (max + min) >> 1;

cec_timer_fn() is a timer callback which reads ce_arr.array[] and updates its decay values. Elements could be added to or removed from this global array in parallel, although the array itself will not grow or shrink. del_lru_elem_unlocked() uses FULL_COUNT() as a key to find a right element to remove, which could be affected by the parallel timer.

Fix this by converting the mutex to a spinlock and holding it inside the timer.

---
 drivers/ras/cec.c | 16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)

index 61332c9aab5a..a82c9d08d47a 100644
@@ -117,7 +117,7 @@ static struct ce_array {
 	};
 } ce_arr;
 
-static DEFINE_MUTEX(ce_mutex);
+static DEFINE_SPINLOCK(ce_lock);
 static u64 dfs_pfn;
 
 /* Amount of errors after which we offline */

@@ -171,7 +171,9 @@ static void cec_mod_timer(struct timer_list *t, unsigned long interval)
 
 static void cec_timer_fn(struct timer_list *unused)
 {
+	spin_lock(&ce_lock);
 	do_spring_cleaning(&ce_arr);
+	spin_unlock(&ce_lock);
 
 	cec_mod_timer(&cec_timer, timer_interval);
 }

@@ -265,9 +267,9 @@ static u64 __maybe_unused del_lru_elem(void)
 	if (!ca->n)
 		return 0;
 
-	mutex_lock(&ce_mutex);
+	spin_lock_bh(&ce_lock);
 	pfn = del_lru_elem_unlocked(ca);
-	mutex_unlock(&ce_mutex);
+	spin_unlock_bh(&ce_lock);
 
 	return pfn;
 }

@@ -288,7 +290,7 @@ int cec_add_elem(u64 pfn)
 
 	ca->ces_entered++;
 
-	mutex_lock(&ce_mutex);
+	spin_lock_bh(&ce_lock);
 
 	if (ca->n == MAX_ELEMS)
 		WARN_ON(!del_lru_elem_unlocked(ca));

@@ -349,7 +351,7 @@ int cec_add_elem(u64 pfn)
 		do_spring_cleaning(ca);
 
 unlock:
-	mutex_unlock(&ce_mutex);
+	spin_unlock_bh(&ce_lock);
 
 	return ret;
 }

@@ -406,7 +408,7 @@ static int array_dump(struct seq_file *m, void *v)
 	u64 prev = 0;
 	int i;
 
-	mutex_lock(&ce_mutex);
+	spin_lock_bh(&ce_lock);
 
 	seq_printf(m, "{ n: %d\n", ca->n);
 	for (i = 0; i < ca->n; i++) {

@@ -431,7 +433,7 @@ static int array_dump(struct seq_file *m, void *v)
 
 	seq_printf(m, "Action threshold: %d\n", count_threshold);
 
-	mutex_unlock(&ce_mutex);
+	spin_unlock_bh(&ce_lock);
 
 	return 0;
 }

I don't understand why mutex is simpler than a spinlock here.

They are just locks requiring different contexts, I don't see how one is simpler than the other. Do you mind to be more specific?

By workqueue, you must mean to say delayed work, right?

But the global workqueue is not serialized either, if you really prefer to move it to a same workqueue for serialization, we have to switch to an ordered workqueue here. It certainly could work, but I don't see how this way is any simpler than just using a spinlock.

What do you think?

Thanks.

Yes, I'd like for this whole CEC code to be lazy and preemptible as it is not at all important when it does its work, as long as it gets it done eventually.

Can't be preemptible with spinlocks.

Serialized with what? Insertions?

That's what the mutex is for and the insertions happen in process context.

So yeah, delayed_work sounds like what it should do. I.e., queue_delayed_work() and decay_interval_set() should do mod_delayed_work(). Something along those lines, anyways.

Thx.

Got it, but the work done with holding a spinlock isn't heavy, given there are only at most 512 elements in the array.

Hmm? We still have to serialize either the timer callback or a delayed work with the rest of array updates (add or delete), right?

As far as I understand, two works in the global workqueue could be still ran in parallel on different CPU's, this is why I said it has to be an ordered queue to guarantee the serialization.

This part is perfectly understood.

Thanks.

Never mind, I think we both agree to hold the mutex inside the work too. I misunderstood it.

I will update my patch to use delayed work.

Thanks.

Sorry, I don't follow.

There's a debugfs interface in /sys/kernel/debug/ras/cec/ with which you can input random PFNs and test the thing.

Show me pls how this can happen with an example.

Thx.

Sorry for the confusion here. Let me try to make it clear with the example I wrote down on a paper before submitting this patch.

Imagine we have the ca->array[] with ca->n = 4, the elements inside are 0, 1, 2, 3. We are trying to find 5 in this array. (This is just to simplify the following iterations of the while loop.)

So in this specific scenario, without my patch we have the following inside the while loop:

min = 0, max = 4
tmp = 2
min = 3, max = 4
tmp = 3
min = 4, max = 4
break

It is okay to have min==4 after this loop as we still need to check if array[4] is whether 5. The problem is array[4] could really be 5 before we delete array[4], so 4 could be returned to caller. And, after that, 4 could be passed to del_elem() inside cec_add_elem(), then the if check inside is passed as it is an unsigned operation, then the memmove() accesses index 5...

To actually crash the kernel, we have to replace 4 with MAX_ELEMS in the above example, kernel would crash either when reading array[MAX_ELEMS] or in the memmove().

Let me try if I can figure out how to add and remove PFN's.

Thanks.

The array of previously seen pfn values is one page.

The problem case occurs when we've seen enough distinct errors that we have filled every entry, then we try to look up a pfn that is larger that any seen before.

The loop:

	while (min < max) {
		...
	}

will terminate with "min" set to MAX_ELEMS. Then we execute:

	this_pfn = PFN(ca->array[min]);

which references beyond the end of the space allocated for ca->array.

Probably won't crash, but we will read a garbage value from whatever memory is allocated next.

Chances are high that the test:

	if (this_pfn == pfn)

won't find that the garbage value matches the pfn that we were looking for ... so we will likley be lucky and not do anything too dumb. But we shouldn't just cross our fingers and hope.

Fix looks mostly OK, but we should probably move the

	if (to)
		*to = min;

inside the new

	if (min < ca->n) {
		...
	}

clause.

-Tony

Exactly.

It will eventually crash, this can be proved. :)

No, we can't, in case of -ENOKEY, we still have to save the index for caller to insert it at the end of the array, therefore *to must be always saved.

Thanks.

Hmmm. But can we ever really have this happen? The call sequence to get here looks like:

        mutex_lock(&ce_mutex);

        if (ca->n == MAX_ELEMS)
                WARN_ON(!del_lru_elem_unlocked(ca));

        ret = find_elem(ca, pfn, &to);

I.e. if the array was all the way full, we delete one element before calling find_elem(). So when we get here:

static int __find_elem(struct ce_array *ca, u64 pfn, unsigned int *to)

{
        u64 this_pfn;
        int min = 0, max = ca->n;

The biggest value "max" can have is MAX_ELEMS-1

-Tony

This is exactly the explanation for why the crash is inside memmove() rather than inside find_elem(). del_elem() actually accesses off-by-two once we pass its 'if' check in line 232:

229 static void del_elem(struct ce_array *ca, int idx) 230 {
231 /* Save us a function call when deleting the last element. */
232 if (ca->n - (idx + 1))
233 memmove((void *)&ca->array[idx],
234 (void *)&ca->array[idx + 1],
235 (ca->n - (idx + 1)) * sizeof(u64));
236
237 ca->n--;
238 }

idx is ca->n and ca->n is MAX_ELEMS-1, then the above if statement becomes true, therefore idx+1 is MAX_ELEMS which is just beyond the valid range.

Thanks.

Is that really the memmove() where we die? It looks like it has a special case for dealing with the last element.

But this:

296 ret = find_elem(ca, pfn, &to);
297 if (ret < 0) {
298 /*
299 * Shift range [to-end] to make room for one more element.
300 */
301 memmove((void *)&ca->array[to + 1],
302 (void *)&ca->array[to],
303 (ca->n - to) * sizeof(u64));
304

looks like it also needs a special case for when "to == MAX_ELEMS-1" (we don't need to memmove).

-Tony

Yes it is, I have a stacktrace in production which clearly shows del_elem.isra.1+0x34/0x40, unlike the one I triggered via fake PFN's. I can show you if you want, it is on 4.14, so very unlikely it is interesting to anyone here.

In the specific I talked about, find_elem() returns non-negative, so it won't even hit this branch. Remember how it passed the if check (this_pfn == pfn)? ;)

Thanks.

Correct myself:

The one triggered via fake PFN's also shows
del_elem.constprop.1+0x39/0x40.

Sorry for the mistake, I kinda read into another crash...

Ok. Now I follow what you are saying. I'll try to rephrase here.

1) Initial setup is that we filled the array. Set the threshold to a low value, and then repeatedly added a new pfn (with a value higher than any in the array).

2) First time:
We find the array is full, so delete one item. Add the new pfn to the end (in slot MAX_ELEM-1)

3) Next time. Array is full. Delete one item (assume not the one for our target pfn). This moved our target to slot MAX_ELEM-2.

4) Next time. Array isn't full. We get a hit on our pfn. Bump the count. Find that it exceeded the threshold, so ask to offline it. We delete this from the array. It is a tail deletion so we just decrement ca->n.

5) Final time. Array isn't full. When we look for our pfn in the array it isn't in the array[0,ca->n) range. So we ought to return ENOKEY. But we don't. When we fall out of the search loop:

136 while (min < max) {
137 int tmp = (max + min) >> 1;
138
139 this_pfn = PFN(ca->array[tmp]);
140
141 if (this_pfn < pfn)
142 min = tmp + 1;
143 else if (this_pfn > pfn)
144 max = tmp;
145 else {
146 min = tmp;
147 break;
148 }
149 }

We exit because "min" is not less than "max". We assign "*to" with the index of the available slot.

151 if (to)
152 *to = min;

This line is just wrong. "min" is still within the allocated bounds of the array, but the value is "ca->n", i.e. the first unused slot. The "garbage" value we pick up from here is what was last assigned to the slot when it was valid. Because we have been adding the same pfn over and over, the value we pick up is the pfn that we "deleted" in step "4" above. But remember we deleted it just by adjusting ca->n, not by overwriting this entry.

154 this_pfn = PFN(ca->array[min]);

So now this test succeeds, when it should fail. We return an index of "ca->n".
156 if (this_pfn == pfn)
157 return min;
158
159 return -ENOKEY;

Things go downhill fast from here. We update the count for this entry. Find it is above the threshold, so offline the page and try to delete.

226 static void del_elem(struct ce_array *ca, int idx) 227 {
228 /* Save us a function call when deleting the last element. */

idx is equal to ca->n. So this is "if (-1)" ... so we decide we need to memmove some entries. The array indices "idx" and "idx+1" are not out of bounds for the allocated size, but they aren't what we want. The real problem is the count passed to memmove.

229 if (ca->n - (idx + 1))
230 memmove((void *)&ca->array[idx],
231 (void *)&ca->array[idx + 1],
232 (ca->n - (idx + 1)) * sizeof(u64));
233
234 ca->n--;
235 }

So I'm now liking this version of the patch by Cong:

index 2d9ec378a8bc..b7cb0b9b1346 100644
@@ -204,10 +204,12 @@ static int __find_elem(struct ce_array *ca, u64 pfn, unsigned int *to)
 	if (to)
 		*to = min;
 
-	this_pfn = PFN(ca->array[min]);
+	if (min < ca->n) {
+		this_pfn = PFN(ca->array[min]);
 
-	if (this_pfn == pfn)
-		return min;
+		if (this_pfn == pfn)
+			return min;
+	}
 
 	return -ENOKEY;
 }

Yes, your detailed analysis is correct. Sorry if I caused any confusion here.

...

Thanks for reviewing my patch!