Skip to contentSkip to conversation

mm/swapfile.c: simplify the scan loop in scan_swap_map_slots()

PATCH In review Wei Yang 2 participants 11 messages Apr 22, 2020 – Apr 29, 2020

Subsystems (2)
lore
Share & tools
lore

Wei Yang

author
#0 lore raw

PATCH v2 1/1 mm/swapfile.c: simplify the scan loop in scan_swap_map_slots()

After commit c60aa176c6de8 ("swapfile: swap allocation cycle if nonrot"), swap allocation is cyclic. Current approach is done with two separate loop on the upper and lower half. This looks a little redundant.

From another point of view, the loop iterates [lowest_bit, highest_bit] range starting with (offset + 1) but except scan_base. So we can simplify the loop with condition (next_offset() != scan_base) by introducing next_offset() which makes sure offset fit in that range with correct order.

CC Hugh Dickins <[email protected]>
CC "Huang, Ying" <[email protected]>

---
v2:
* return scan_base if the lower part is eaten
* only start over when iterating on the upper part

---
 mm/swapfile.c | 31 ++++++++++++++-----------------
 1 file changed, 14 insertions(+), 17 deletions(-)
mm/swapfile.c +14 -17
index f903e5a165d5..0005a4a1c1b4 100644
@@ -729,6 +729,19 @@ static void swap_range_free(struct swap_info_struct *si, unsigned long offset,
 	}
 }
 
+static unsigned long next_offset(struct swap_info_struct *si,
+				unsigned long *offset, unsigned long scan_base)
+{
+	/* only start over when iterating on the upper part */
+	if (++(*offset) > si->highest_bit && *offset > scan_base) {
+		*offset = si->lowest_bit;
+		/* someone has eaten the lower part */
+		if (si->lowest_bit >= scan_base)
+			return scan_base;
+	}
+	return *offset;
+}
+
 static int scan_swap_map_slots(struct swap_info_struct *si,
 			       unsigned char usage, int nr,
 			       swp_entry_t slots[])
@@ -876,22 +889,7 @@ static int scan_swap_map_slots(struct swap_info_struct *si,
 
 scan:
 	spin_unlock(&si->lock);
-	while (++offset <= si->highest_bit) {
-		if (!si->swap_map[offset]) {
-			spin_lock(&si->lock);
-			goto checks;
-		}
-		if (vm_swap_full() && si->swap_map[offset] == SWAP_HAS_CACHE) {
-			spin_lock(&si->lock);
-			goto checks;
-		}
-		if (unlikely(--latency_ration < 0)) {
-			cond_resched();
-			latency_ration = LATENCY_LIMIT;
-		}
-	}
-	offset = si->lowest_bit;
-	while (offset < scan_base) {
+	while (next_offset(si, &offset, scan_base) != scan_base) {
 		if (!si->swap_map[offset]) {
 			spin_lock(&si->lock);
 			goto checks;
@@ -904,7 +902,6 @@ static int scan_swap_map_slots(struct swap_info_struct *si,
 			cond_resched();
 			latency_ration = LATENCY_LIMIT;
 		}
-		offset++;
 	}
 	spin_lock(&si->lock);
 
Signature · 1 line
2.23.0
#1 lore raw
Quoted 4 lines · Wei Yang

After commit c60aa176c6de8 ("swapfile: swap allocation cycle if nonrot"), swap allocation is cyclic. Current approach is done with two separate loop on the upper and lower half. This looks a little redundant.

I can understand that the redundant code doesn't smell good. But I don't think the new code is easier to be understood than the original one.

Quoted 26 lines

From another point of view, the loop iterates [lowest_bit, highest_bit] range starting with (offset + 1) but except scan_base. So we can simplify the loop with condition (next_offset() != scan_base) by introducing next_offset() which makes sure offset fit in that range with correct order.

CC Hugh Dickins <[email protected]>
CC "Huang, Ying" <[email protected]>

---
v2:
* return scan_base if the lower part is eaten
* only start over when iterating on the upper part

---
 mm/swapfile.c | 31 ++++++++++++++-----------------
 1 file changed, 14 insertions(+), 17 deletions(-)
mm/swapfile.c +0 -0
index f903e5a165d5..0005a4a1c1b4 100644
@@ -729,6 +729,19 @@ static void swap_range_free(struct swap_info_struct *si, unsigned long offset,
 	}
 }
 

mm/swapfile.c static void swap_range_free(struct swap_info_struct *si, unsigned long offset, · line 741

Quoted 10 lines
mm/swapfile.c +10 -0
+static unsigned long next_offset(struct swap_info_struct *si,
+				unsigned long *offset, unsigned long scan_base)
+{
+	/* only start over when iterating on the upper part */
+	if (++(*offset) > si->highest_bit && *offset > scan_base) {
+		*offset = si->lowest_bit;
+		/* someone has eaten the lower part */
+		if (si->lowest_bit >= scan_base)
+			return scan_base;
+	}

if "offset > si->highest_bit" is true and "offset < scan_base" is true, scan_base need to be returned.

Again, the new code doesn't make it easier to find this kind of issues.

Best Regards,
Huang, Ying

author
#2 lore raw
Quoted 37 lines · Ying
Quoted 4 lines · Wei Yang

After commit c60aa176c6de8 ("swapfile: swap allocation cycle if nonrot"), swap allocation is cyclic. Current approach is done with two separate loop on the upper and lower half. This looks a little redundant.

I can understand that the redundant code doesn't smell good. But I don't think the new code is easier to be understood than the original one.

Quoted 26 lines

From another point of view, the loop iterates [lowest_bit, highest_bit] range starting with (offset + 1) but except scan_base. So we can simplify the loop with condition (next_offset() != scan_base) by introducing next_offset() which makes sure offset fit in that range with correct order.

CC Hugh Dickins <[email protected]>
CC "Huang, Ying" <[email protected]>

---
v2:
* return scan_base if the lower part is eaten
* only start over when iterating on the upper part

---
 mm/swapfile.c | 31 ++++++++++++++-----------------
 1 file changed, 14 insertions(+), 17 deletions(-)
mm/swapfile.c +0 -0
index f903e5a165d5..0005a4a1c1b4 100644
@@ -729,6 +729,19 @@ static void swap_range_free(struct swap_info_struct *si, unsigned long offset,
 	}
 }
 
Quoted 14 lines

mm/swapfile.c static void swap_range_free(struct swap_info_struct *si, unsigned long offset, · line 741

Quoted 10 lines
mm/swapfile.c +10 -0
+static unsigned long next_offset(struct swap_info_struct *si,
+				unsigned long *offset, unsigned long scan_base)
+{
+	/* only start over when iterating on the upper part */
+	if (++(*offset) > si->highest_bit && *offset > scan_base) {
+		*offset = si->lowest_bit;
+		/* someone has eaten the lower part */
+		if (si->lowest_bit >= scan_base)
+			return scan_base;
+	}

if "offset > si->highest_bit" is true and "offset < scan_base" is true, scan_base need to be returned.

When this case would happen in the original code?

Quoted 4 lines

Again, the new code doesn't make it easier to find this kind of issues.

Best Regards,
Huang, Ying

Signature · 2 lines
Wei Yang
Help you, Help me
#3 lore raw
Quoted 53 lines · Wei Yang
Quoted 37 lines · Ying
Quoted 4 lines · Wei Yang

After commit c60aa176c6de8 ("swapfile: swap allocation cycle if nonrot"), swap allocation is cyclic. Current approach is done with two separate loop on the upper and lower half. This looks a little redundant.

I can understand that the redundant code doesn't smell good. But I don't think the new code is easier to be understood than the original one.

Quoted 26 lines

From another point of view, the loop iterates [lowest_bit, highest_bit] range starting with (offset + 1) but except scan_base. So we can simplify the loop with condition (next_offset() != scan_base) by introducing next_offset() which makes sure offset fit in that range with correct order.

CC Hugh Dickins <[email protected]>
CC "Huang, Ying" <[email protected]>

---
v2:
* return scan_base if the lower part is eaten
* only start over when iterating on the upper part

---
 mm/swapfile.c | 31 ++++++++++++++-----------------
 1 file changed, 14 insertions(+), 17 deletions(-)
mm/swapfile.c +0 -0
index f903e5a165d5..0005a4a1c1b4 100644
@@ -729,6 +729,19 @@ static void swap_range_free(struct swap_info_struct *si, unsigned long offset,
 	}
 }
 
Quoted 14 lines

mm/swapfile.c static void swap_range_free(struct swap_info_struct *si, unsigned long offset, · line 741

Quoted 10 lines
mm/swapfile.c +10 -0
+static unsigned long next_offset(struct swap_info_struct *si,
+				unsigned long *offset, unsigned long scan_base)
+{
+	/* only start over when iterating on the upper part */
+	if (++(*offset) > si->highest_bit && *offset > scan_base) {
+		*offset = si->lowest_bit;
+		/* someone has eaten the lower part */
+		if (si->lowest_bit >= scan_base)
+			return scan_base;
+	}

if "offset > si->highest_bit" is true and "offset < scan_base" is true, scan_base need to be returned.

Quoted 1 line

When this case would happen in the original code?

In the original code, the loop can still stop.

Best Regards,
Huang, Ying

Quoted 4 lines
Quoted 4 lines

Again, the new code doesn't make it easier to find this kind of issues.

Best Regards,
Huang, Ying

author
#4 lore raw
Quoted 2 lines · Ying

Wei Yang <[email protected]> writes:

[...]

Quoted 9 lines
Quoted 6 lines
Quoted 4 lines

if "offset > si->highest_bit" is true and "offset < scan_base" is true, scan_base need to be returned.

When this case would happen in the original code?

In the original code, the loop can still stop.

Sorry, I don't get your point yet.

In original code, there are two separate loops

    while (++offset <= si->highest_bit) {
    }

    while (offset < scan_base) {
    }

And for your condition, (offset > highest_bit) && (offset < scan_base), which terminates the first loop and fits the second loop well.

Not sure how this condition would stop the loop in original code?

Quoted 7 lines

Best Regards,
Huang, Ying

Quoted 4 lines
Quoted 4 lines

Again, the new code doesn't make it easier to find this kind of issues.

Best Regards,
Huang, Ying

Signature · 2 lines
Wei Yang
Help you, Help me
#5 lore raw
Quoted 24 lines · Wei Yang
Quoted 2 lines · Ying

Wei Yang <[email protected]> writes:

[...]

Quoted 9 lines
Quoted 6 lines
Quoted 4 lines

if "offset > si->highest_bit" is true and "offset < scan_base" is true, scan_base need to be returned.

When this case would happen in the original code?

In the original code, the loop can still stop.

Sorry, I don't get your point yet.

In original code, there are two separate loops

    while (++offset <= si->highest_bit) {
    }

    while (offset < scan_base) {
    }
Quoted 4 lines

And for your condition, (offset > highest_bit) && (offset < scan_base), which terminates the first loop and fits the second loop well.

Not sure how this condition would stop the loop in original code?

Per my understanding, in your code, if some other task changes si->highest_bit to be less than scan_base in parallel. The loop may cannot stop.

Best Regards,
Huang, Ying

Quoted 7 lines
Quoted 7 lines

Best Regards,
Huang, Ying

Quoted 4 lines
Quoted 4 lines

Again, the new code doesn't make it easier to find this kind of issues.

Best Regards,
Huang, Ying

author
#6 lore raw
Quoted 26 lines · Ying
Quoted 24 lines · Wei Yang
Quoted 2 lines · Ying

Wei Yang <[email protected]> writes:

[...]

Quoted 9 lines
Quoted 6 lines
Quoted 4 lines

if "offset > si->highest_bit" is true and "offset < scan_base" is true, scan_base need to be returned.

When this case would happen in the original code?

In the original code, the loop can still stop.

Sorry, I don't get your point yet.

In original code, there are two separate loops

    while (++offset <= si->highest_bit) {
    }

    while (offset < scan_base) {
    }
Quoted 8 lines
Quoted 4 lines

And for your condition, (offset > highest_bit) && (offset < scan_base), which terminates the first loop and fits the second loop well.

Not sure how this condition would stop the loop in original code?

Per my understanding, in your code, if some other task changes si->highest_bit to be less than scan_base in parallel. The loop may cannot stop.

When (offset > scan_base), (offset > si->highest_bit) means offset will be set to si->lowest_bit.

When (offset < scan_base), next_offset() would always increase offset till offset is scan_base.

Sorry, I didn't catch your case. Would you minding giving more detail?

Quoted 11 lines

Best Regards,
Huang, Ying

Quoted 7 lines
Quoted 7 lines

Best Regards,
Huang, Ying

Quoted 4 lines
Quoted 4 lines

Again, the new code doesn't make it easier to find this kind of issues.

Best Regards,
Huang, Ying

Signature · 2 lines
Wei Yang
Help you, Help me
#7 lore raw
Quoted 36 lines · Wei Yang
Quoted 26 lines · Ying
Quoted 24 lines · Wei Yang
Quoted 2 lines · Ying

Wei Yang <[email protected]> writes:

[...]

Quoted 9 lines
Quoted 6 lines
Quoted 4 lines

if "offset > si->highest_bit" is true and "offset < scan_base" is true, scan_base need to be returned.

When this case would happen in the original code?

In the original code, the loop can still stop.

Sorry, I don't get your point yet.

In original code, there are two separate loops

    while (++offset <= si->highest_bit) {
    }

    while (offset < scan_base) {
    }
Quoted 8 lines
Quoted 4 lines

And for your condition, (offset > highest_bit) && (offset < scan_base), which terminates the first loop and fits the second loop well.

Not sure how this condition would stop the loop in original code?

Per my understanding, in your code, if some other task changes si->highest_bit to be less than scan_base in parallel. The loop may cannot stop.

Quoted 7 lines

When (offset > scan_base), (offset > si->highest_bit) means offset will be set to si->lowest_bit.

When (offset < scan_base), next_offset() would always increase offset till offset is scan_base.

Sorry, I didn't catch your case. Would you minding giving more detail?

Don't think in single thread model. There's no lock to prevent other tasks to change si->highest_bit simultaneously. For example, task B may change si->highest_bit to be less than scan_base in task A.

Best Regards,
Huang, Ying

Quoted 11 lines
Quoted 11 lines

Best Regards,
Huang, Ying

Quoted 7 lines
Quoted 7 lines

Best Regards,
Huang, Ying

Quoted 4 lines
Quoted 4 lines

Again, the new code doesn't make it easier to find this kind of issues.

Best Regards,
Huang, Ying

author
#8 lore raw
Quoted 41 lines · Ying
Quoted 39 lines · Wei Yang
Quoted 26 lines · Ying
Quoted 24 lines · Wei Yang
Quoted 2 lines · Ying

Wei Yang <[email protected]> writes:

[...]

Quoted 9 lines
Quoted 6 lines
Quoted 4 lines

if "offset > si->highest_bit" is true and "offset < scan_base" is true, scan_base need to be returned.

When this case would happen in the original code?

In the original code, the loop can still stop.

Sorry, I don't get your point yet.

In original code, there are two separate loops

    while (++offset <= si->highest_bit) {
    }

    while (offset < scan_base) {
    }
Quoted 8 lines
Quoted 4 lines

And for your condition, (offset > highest_bit) && (offset < scan_base), which terminates the first loop and fits the second loop well.

Not sure how this condition would stop the loop in original code?

Per my understanding, in your code, if some other task changes si->highest_bit to be less than scan_base in parallel. The loop may cannot stop.

When (offset > scan_base), (offset > si->highest_bit) means offset will be set to si->lowest_bit.

Quoted 9 lines
Quoted 4 lines

When (offset < scan_base), next_offset() would always increase offset till offset is scan_base.

Sorry, I didn't catch your case. Would you minding giving more detail?

Don't think in single thread model. There's no lock to prevent other tasks to change si->highest_bit simultaneously. For example, task B may change si->highest_bit to be less than scan_base in task A.

Yes, I am trying to think about it in parallel mode.

Here are the cases, it might happen in parallel when task B change highest_bit to be less than scan_base.

(1)
offset
v
+-------------------+------------------+
^ ^ ^
lowest_bit highest_bit scan_base

(2)
offset
v
+-------------------+------------------+
^ ^ ^
lowest_bit highest_bit scan_base

(3)
offset
v
+-------------------+------------------+
^ ^ ^
lowest_bit highest_bit scan_base

Case (1), (offset > highest) && (offset > scan_base), offset would be set to lowest_bit. This looks good.

Case (2), (offset > highest) && (offset < scan_base), since offset is less than scan_base, it wouldn't be set to lowest. Instead it will continue to scan_base.

Case (3), almost the same as Case (2).

In Case (2) and (3), one thing interesting is the loop won't stop at highest_bit, while the behavior is the same as original code.

Maybe your concern is this one? I still not figure out your point about the infinite loop. Hope you would share some light on it.

Quoted 14 lines

Best Regards,
Huang, Ying

Quoted 11 lines
Quoted 11 lines

Best Regards,
Huang, Ying

Quoted 7 lines
Quoted 7 lines

Best Regards,
Huang, Ying

Quoted 4 lines
Quoted 4 lines

Again, the new code doesn't make it easier to find this kind of issues.

Best Regards,
Huang, Ying

Signature · 2 lines
Wei Yang
Help you, Help me
#9 lore raw
Quoted 65 lines · Wei Yang
Quoted 41 lines · Ying
Quoted 39 lines · Wei Yang
Quoted 26 lines · Ying
Quoted 24 lines · Wei Yang
Quoted 2 lines · Ying

Wei Yang <[email protected]> writes:

[...]

Quoted 9 lines
Quoted 6 lines
Quoted 4 lines

if "offset > si->highest_bit" is true and "offset < scan_base" is true, scan_base need to be returned.

When this case would happen in the original code?

In the original code, the loop can still stop.

Sorry, I don't get your point yet.

In original code, there are two separate loops

    while (++offset <= si->highest_bit) {
    }

    while (offset < scan_base) {
    }
Quoted 8 lines
Quoted 4 lines

And for your condition, (offset > highest_bit) && (offset < scan_base), which terminates the first loop and fits the second loop well.

Not sure how this condition would stop the loop in original code?

Per my understanding, in your code, if some other task changes si->highest_bit to be less than scan_base in parallel. The loop may cannot stop.

When (offset > scan_base), (offset > si->highest_bit) means offset will be set to si->lowest_bit.

Quoted 9 lines
Quoted 4 lines

When (offset < scan_base), next_offset() would always increase offset till offset is scan_base.

Sorry, I didn't catch your case. Would you minding giving more detail?

Don't think in single thread model. There's no lock to prevent other tasks to change si->highest_bit simultaneously. For example, task B may change si->highest_bit to be less than scan_base in task A.

Yes, I am trying to think about it in parallel mode.

Here are the cases, it might happen in parallel when task B change highest_bit to be less than scan_base.

(1)
offset
v
+-------------------+------------------+
^ ^ ^
lowest_bit highest_bit scan_base

Quoted 7 lines

(2)
offset
v
+-------------------+------------------+
^ ^ ^
lowest_bit highest_bit scan_base

This is the case in my mind. But my original understanding to your code wasn't correct. As you said, loop can stop because offset is kept increasing. Sorry about that.

But I still don't like your new code. It's not as obvious as the original one.

Best Regards,
Huang, Ying

Quoted 37 lines

(3)
offset
v
+-------------------+------------------+
^ ^ ^
lowest_bit highest_bit scan_base

Case (1), (offset > highest) && (offset > scan_base), offset would be set to lowest_bit. This looks good.

Case (2), (offset > highest) && (offset < scan_base), since offset is less than scan_base, it wouldn't be set to lowest. Instead it will continue to scan_base.

Case (3), almost the same as Case (2).

In Case (2) and (3), one thing interesting is the loop won't stop at highest_bit, while the behavior is the same as original code.

Maybe your concern is this one? I still not figure out your point about the infinite loop. Hope you would share some light on it.

Quoted 14 lines

Best Regards,
Huang, Ying

Quoted 11 lines
Quoted 11 lines

Best Regards,
Huang, Ying

Quoted 7 lines
Quoted 7 lines

Best Regards,
Huang, Ying

Quoted 4 lines
Quoted 4 lines

Again, the new code doesn't make it easier to find this kind of issues.

Best Regards,
Huang, Ying

author
#10 lore raw
Quoted 75 lines · Ying
Quoted 65 lines · Wei Yang
Quoted 41 lines · Ying
Quoted 39 lines · Wei Yang
Quoted 26 lines · Ying
Quoted 24 lines · Wei Yang
Quoted 2 lines · Ying

Wei Yang <[email protected]> writes:

[...]

Quoted 9 lines
Quoted 6 lines
Quoted 4 lines

if "offset > si->highest_bit" is true and "offset < scan_base" is true, scan_base need to be returned.

When this case would happen in the original code?

In the original code, the loop can still stop.

Sorry, I don't get your point yet.

In original code, there are two separate loops

    while (++offset <= si->highest_bit) {
    }

    while (offset < scan_base) {
    }
Quoted 8 lines
Quoted 4 lines

And for your condition, (offset > highest_bit) && (offset < scan_base), which terminates the first loop and fits the second loop well.

Not sure how this condition would stop the loop in original code?

Per my understanding, in your code, if some other task changes si->highest_bit to be less than scan_base in parallel. The loop may cannot stop.

When (offset > scan_base), (offset > si->highest_bit) means offset will be set to si->lowest_bit.

Quoted 9 lines
Quoted 4 lines

When (offset < scan_base), next_offset() would always increase offset till offset is scan_base.

Sorry, I didn't catch your case. Would you minding giving more detail?

Don't think in single thread model. There's no lock to prevent other tasks to change si->highest_bit simultaneously. For example, task B may change si->highest_bit to be less than scan_base in task A.

Yes, I am trying to think about it in parallel mode.

Here are the cases, it might happen in parallel when task B change highest_bit to be less than scan_base.

(1)
offset
v
+-------------------+------------------+
^ ^ ^
lowest_bit highest_bit scan_base

Quoted 7 lines

(2)
offset
v
+-------------------+------------------+
^ ^ ^
lowest_bit highest_bit scan_base

Quoted 4 lines

This is the case in my mind. But my original understanding to your code wasn't correct. As you said, loop can stop because offset is kept increasing. Sorry about that.

NP.

Quoted 2 lines

But I still don't like your new code. It's not as obvious as the original one.

Sure, thanks for your time.

Quoted 41 lines

Best Regards,
Huang, Ying

Quoted 37 lines

(3)
offset
v
+-------------------+------------------+
^ ^ ^
lowest_bit highest_bit scan_base

Case (1), (offset > highest) && (offset > scan_base), offset would be set to lowest_bit. This looks good.

Case (2), (offset > highest) && (offset < scan_base), since offset is less than scan_base, it wouldn't be set to lowest. Instead it will continue to scan_base.

Case (3), almost the same as Case (2).

In Case (2) and (3), one thing interesting is the loop won't stop at highest_bit, while the behavior is the same as original code.

Maybe your concern is this one? I still not figure out your point about the infinite loop. Hope you would share some light on it.

Quoted 14 lines

Best Regards,
Huang, Ying

Quoted 11 lines
Quoted 11 lines

Best Regards,
Huang, Ying

Quoted 7 lines
Quoted 7 lines

Best Regards,
Huang, Ying

Quoted 4 lines
Quoted 4 lines

Again, the new code doesn't make it easier to find this kind of issues.

Best Regards,
Huang, Ying

Signature · 2 lines
Wei Yang
Help you, Help me