Skip to contentSkip to conversation

memblock: don't run loop in memblock_add_range() twice

PATCH In review Yajun Deng 2 participants 5 messages Oct 3, 2023 – Oct 12, 2023

Subsystems (2)
lore
Share & tools
lore

Yajun Deng

author
#0 lore raw

PATCH v3 1/1 memblock: don't run loop in memblock_add_range() twice

There is round twice in memblock_add_range(). The first counts the number of regions needed to accommodate the new area. The second actually inserts them. But the first round isn't really needed, we just need to check the counts before inserting them.

Check the count before memblock_insert_region. If the count is equal to the maximum, it needs to resize the array. Otherwise, insert it directly.

Also, there is a nested call here, we need to reserve the current array immediately if slab is unavailable.

---
v3: reserve the current array immediately if slab is unavailable.
v2: remove the changes of memblock_double_array.
v1: https://lore.kernel.org/all/[email protected]/

---
 mm/memblock.c | 93 +++++++++++++++++++++++----------------------------
 1 file changed, 41 insertions(+), 52 deletions(-)
mm/memblock.c +41 -52
index 5a88d6d24d79..71449c0b8bc8 100644
@@ -588,11 +588,12 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 				phys_addr_t base, phys_addr_t size,
 				int nid, enum memblock_flags flags)
 {
-	bool insert = false;
 	phys_addr_t obase = base;
 	phys_addr_t end = base + memblock_cap_size(base, &size);
-	int idx, nr_new, start_rgn = -1, end_rgn;
+	int idx, start_rgn = -1, end_rgn;
 	struct memblock_region *rgn;
+	int use_slab = slab_is_available();
+	unsigned long ocnt = type->cnt;
 
 	if (!size)
 		return 0;
@@ -608,25 +609,6 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 		return 0;
 	}
 
-	/*
-	 * The worst case is when new range overlaps all existing regions,
-	 * then we'll need type->cnt + 1 empty regions in @type. So if
-	 * type->cnt * 2 + 1 is less than or equal to type->max, we know
-	 * that there is enough empty regions in @type, and we can insert
-	 * regions directly.
-	 */
-	if (type->cnt * 2 + 1 <= type->max)
-		insert = true;
-
-repeat:
-	/*
-	 * The following is executed twice.  Once with %false @insert and
-	 * then with %true.  The first counts the number of regions needed
-	 * to accommodate the new area.  The second actually inserts them.
-	 */
-	base = obase;
-	nr_new = 0;
-
 	for_each_memblock_type(idx, type, rgn) {
 		phys_addr_t rbase = rgn->base;
 		phys_addr_t rend = rbase + rgn->size;
@@ -644,15 +626,30 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 			WARN_ON(nid != memblock_get_region_node(rgn));
 #endif
 			WARN_ON(flags != rgn->flags);
-			nr_new++;
-			if (insert) {
-				if (start_rgn == -1)
-					start_rgn = idx;
-				end_rgn = idx + 1;
-				memblock_insert_region(type, idx++, base,
-						       rbase - base, nid,
-						       flags);
+
+			/*
+			 * If type->cnt is equal to type->max, it means there's
+			 * not enough empty region and the array needs to be
+			 * resized. Otherwise, insert it directly.
+			 *
+			 * If slab is unavailable, it means a new array was reserved
+			 * in memblock_double_array. There is a nested call here, We
+			 * need to reserve the current array now if its type is
+			 * reserved.
+			 */
+			if (type->cnt == type->max) {
+				if (memblock_double_array(type, obase, size))
+					return -ENOMEM;
+				else if (!use_slab && type == &memblock.reserved)
+					return memblock_reserve(obase, size);
 			}
+
+			if (start_rgn == -1)
+				start_rgn = idx;
+			end_rgn = idx + 1;
+			memblock_insert_region(type, idx++, base,
+					       rbase - base, nid,
+					       flags);
 		}
 		/* area below @rend is dealt with, forget about it */
 		base = min(rend, end);
@@ -660,33 +657,25 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 
 	/* insert the remaining portion */
 	if (base < end) {
-		nr_new++;
-		if (insert) {
-			if (start_rgn == -1)
-				start_rgn = idx;
-			end_rgn = idx + 1;
-			memblock_insert_region(type, idx, base, end - base,
-					       nid, flags);
+
+		if (type->cnt == type->max) {
+			if (memblock_double_array(type, obase, size))
+				return -ENOMEM;
+			else if (!use_slab && type == &memblock.reserved)
+				return memblock_reserve(obase, size);
 		}
-	}
 
-	if (!nr_new)
-		return 0;
+		if (start_rgn == -1)
+			start_rgn = idx;
+		end_rgn = idx + 1;
+		memblock_insert_region(type, idx, base, end - base,
+				       nid, flags);
+	}
 
-	/*
-	 * If this was the first round, resize array and repeat for actual
-	 * insertions; otherwise, merge and return.
-	 */
-	if (!insert) {
-		while (type->cnt + nr_new > type->max)
-			if (memblock_double_array(type, obase, size) < 0)
-				return -ENOMEM;
-		insert = true;
-		goto repeat;
-	} else {
+	if (ocnt != type->cnt)
 		memblock_merge_regions(type, start_rgn, end_rgn);
-		return 0;
-	}
+
+	return 0;
 }
 
 /**
Signature · 1 line
2.25.1
maintainer
#1 lore raw
Quoted 10 lines · Yajun Deng

There is round twice in memblock_add_range(). The first counts the number of regions needed to accommodate the new area. The second actually inserts them. But the first round isn't really needed, we just need to check the counts before inserting them.

Check the count before memblock_insert_region. If the count is equal to the maximum, it needs to resize the array. Otherwise, insert it directly.

Also, there is a nested call here, we need to reserve the current array immediately if slab is unavailable.

I presume this fixes a bug you found in v2, but are you sure it'll _never_ explode on a machine with different memory layout and different sequence of memblock_reservee() calls?

I don't see this micro-optimization is worth the churn and potential bugs. NAK.

Quoted 145 lines

---
v3: reserve the current array immediately if slab is unavailable.
v2: remove the changes of memblock_double_array.
v1: https://lore.kernel.org/all/[email protected]/

---
 mm/memblock.c | 93 +++++++++++++++++++++++----------------------------
 1 file changed, 41 insertions(+), 52 deletions(-)
mm/memblock.c +41 -52
index 5a88d6d24d79..71449c0b8bc8 100644
@@ -588,11 +588,12 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 				phys_addr_t base, phys_addr_t size,
 				int nid, enum memblock_flags flags)
 {
-	bool insert = false;
 	phys_addr_t obase = base;
 	phys_addr_t end = base + memblock_cap_size(base, &size);
-	int idx, nr_new, start_rgn = -1, end_rgn;
+	int idx, start_rgn = -1, end_rgn;
 	struct memblock_region *rgn;
+	int use_slab = slab_is_available();
+	unsigned long ocnt = type->cnt;
 
 	if (!size)
 		return 0;
@@ -608,25 +609,6 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 		return 0;
 	}
 
-	/*
-	 * The worst case is when new range overlaps all existing regions,
-	 * then we'll need type->cnt + 1 empty regions in @type. So if
-	 * type->cnt * 2 + 1 is less than or equal to type->max, we know
-	 * that there is enough empty regions in @type, and we can insert
-	 * regions directly.
-	 */
-	if (type->cnt * 2 + 1 <= type->max)
-		insert = true;
-
-repeat:
-	/*
-	 * The following is executed twice.  Once with %false @insert and
-	 * then with %true.  The first counts the number of regions needed
-	 * to accommodate the new area.  The second actually inserts them.
-	 */
-	base = obase;
-	nr_new = 0;
-
 	for_each_memblock_type(idx, type, rgn) {
 		phys_addr_t rbase = rgn->base;
 		phys_addr_t rend = rbase + rgn->size;
@@ -644,15 +626,30 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 			WARN_ON(nid != memblock_get_region_node(rgn));
 #endif
 			WARN_ON(flags != rgn->flags);
-			nr_new++;
-			if (insert) {
-				if (start_rgn == -1)
-					start_rgn = idx;
-				end_rgn = idx + 1;
-				memblock_insert_region(type, idx++, base,
-						       rbase - base, nid,
-						       flags);
+
+			/*
+			 * If type->cnt is equal to type->max, it means there's
+			 * not enough empty region and the array needs to be
+			 * resized. Otherwise, insert it directly.
+			 *
+			 * If slab is unavailable, it means a new array was reserved
+			 * in memblock_double_array. There is a nested call here, We
+			 * need to reserve the current array now if its type is
+			 * reserved.
+			 */
+			if (type->cnt == type->max) {
+				if (memblock_double_array(type, obase, size))
+					return -ENOMEM;
+				else if (!use_slab && type == &memblock.reserved)
+					return memblock_reserve(obase, size);
 			}
+
+			if (start_rgn == -1)
+				start_rgn = idx;
+			end_rgn = idx + 1;
+			memblock_insert_region(type, idx++, base,
+					       rbase - base, nid,
+					       flags);
 		}
 		/* area below @rend is dealt with, forget about it */
 		base = min(rend, end);
@@ -660,33 +657,25 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 
 	/* insert the remaining portion */
 	if (base < end) {
-		nr_new++;
-		if (insert) {
-			if (start_rgn == -1)
-				start_rgn = idx;
-			end_rgn = idx + 1;
-			memblock_insert_region(type, idx, base, end - base,
-					       nid, flags);
+
+		if (type->cnt == type->max) {
+			if (memblock_double_array(type, obase, size))
+				return -ENOMEM;
+			else if (!use_slab && type == &memblock.reserved)
+				return memblock_reserve(obase, size);
 		}
-	}
 
-	if (!nr_new)
-		return 0;
+		if (start_rgn == -1)
+			start_rgn = idx;
+		end_rgn = idx + 1;
+		memblock_insert_region(type, idx, base, end - base,
+				       nid, flags);
+	}
 
-	/*
-	 * If this was the first round, resize array and repeat for actual
-	 * insertions; otherwise, merge and return.
-	 */
-	if (!insert) {
-		while (type->cnt + nr_new > type->max)
-			if (memblock_double_array(type, obase, size) < 0)
-				return -ENOMEM;
-		insert = true;
-		goto repeat;
-	} else {
+	if (ocnt != type->cnt)
 		memblock_merge_regions(type, start_rgn, end_rgn);
-		return 0;
-	}
+
+	return 0;
 }
 
 /**
Signature · 1 line
2.25.1
Signature · 2 lines
Sincerely yours,
Mike.
author
#2 lore raw
Quoted 6 lines · Mike Rapoport
Quoted 5 lines · Yajun Deng

There is round twice in memblock_add_range(). The first counts the number of regions needed to accommodate the new area. The second actually inserts them. But the first round isn't really needed, we just need to check the counts before inserting them.

Quoted 8 lines
Quoted 5 lines

Check the count before memblock_insert_region. If the count is equal to the maximum, it needs to resize the array. Otherwise, insert it directly.

Also, there is a nested call here, we need to reserve the current array immediately if slab is unavailable.

I presume this fixes a bug you found in v2, but are you sure it'll _never_ explode on a machine with different memory layout and different sequence of memblock_reservee() calls?

Not really. It has become complex. Because it has to deal with the nested call.

I think v1 is the best solution if you accept it. It doesn't need to deal with the nested call. It would be safer.

I don't think we must do memblock_reserve() in memblock_double_array(). These parameters 'addr' and

'new_alloc_size' in memblock_reserve come from memblock_find_in_range(). Since we can handle these

parameters out of memblock_find_in_range(), we can also handle 'addr' and 'new_alloc_size' out of

memblock_double_array().

Quoted 2 lines

I don't see this micro-optimization is worth the churn and potential bugs. NAK.

There are many handouts that tell people it needs to run twice in memblock_add_range().

I think it's time to change this. I'm trying to tell people that running twice is unnecessary.

Like v1, it just needs to check the count and handle memblock_reserve out of memblock_double_array.

Quoted 146 lines
Quoted 146 lines

---
v3: reserve the current array immediately if slab is unavailable.
v2: remove the changes of memblock_double_array.
v1: https://lore.kernel.org/all/[email protected]/

---
  mm/memblock.c | 93 +++++++++++++++++++++++----------------------------
  1 file changed, 41 insertions(+), 52 deletions(-)
mm/memblock.c +41 -52
index 5a88d6d24d79..71449c0b8bc8 100644
@@ -588,11 +588,12 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
  				phys_addr_t base, phys_addr_t size,
  				int nid, enum memblock_flags flags)
  {
-	bool insert = false;
  	phys_addr_t obase = base;
  	phys_addr_t end = base + memblock_cap_size(base, &size);
-	int idx, nr_new, start_rgn = -1, end_rgn;
+	int idx, start_rgn = -1, end_rgn;
  	struct memblock_region *rgn;
+	int use_slab = slab_is_available();
+	unsigned long ocnt = type->cnt;
 
  	if (!size)
  		return 0;
@@ -608,25 +609,6 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
  		return 0;
  	}
 
-	/*
-	 * The worst case is when new range overlaps all existing regions,
-	 * then we'll need type->cnt + 1 empty regions in @type. So if
-	 * type->cnt * 2 + 1 is less than or equal to type->max, we know
-	 * that there is enough empty regions in @type, and we can insert
-	 * regions directly.
-	 */
-	if (type->cnt * 2 + 1 <= type->max)
-		insert = true;
-
-repeat:
-	/*
-	 * The following is executed twice.  Once with %false @insert and
-	 * then with %true.  The first counts the number of regions needed
-	 * to accommodate the new area.  The second actually inserts them.
-	 */
-	base = obase;
-	nr_new = 0;
-
  	for_each_memblock_type(idx, type, rgn) {
  		phys_addr_t rbase = rgn->base;
  		phys_addr_t rend = rbase + rgn->size;
@@ -644,15 +626,30 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
  			WARN_ON(nid != memblock_get_region_node(rgn));
  #endif
  			WARN_ON(flags != rgn->flags);
-			nr_new++;
-			if (insert) {
-				if (start_rgn == -1)
-					start_rgn = idx;
-				end_rgn = idx + 1;
-				memblock_insert_region(type, idx++, base,
-						       rbase - base, nid,
-						       flags);
+
+			/*
+			 * If type->cnt is equal to type->max, it means there's
+			 * not enough empty region and the array needs to be
+			 * resized. Otherwise, insert it directly.
+			 *
+			 * If slab is unavailable, it means a new array was reserved
+			 * in memblock_double_array. There is a nested call here, We
+			 * need to reserve the current array now if its type is
+			 * reserved.
+			 */
+			if (type->cnt == type->max) {
+				if (memblock_double_array(type, obase, size))
+					return -ENOMEM;
+				else if (!use_slab && type == &memblock.reserved)
+					return memblock_reserve(obase, size);
  			}
+
+			if (start_rgn == -1)
+				start_rgn = idx;
+			end_rgn = idx + 1;
+			memblock_insert_region(type, idx++, base,
+					       rbase - base, nid,
+					       flags);
  		}
  		/* area below @rend is dealt with, forget about it */
  		base = min(rend, end);
@@ -660,33 +657,25 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 
  	/* insert the remaining portion */
  	if (base < end) {
-		nr_new++;
-		if (insert) {
-			if (start_rgn == -1)
-				start_rgn = idx;
-			end_rgn = idx + 1;
-			memblock_insert_region(type, idx, base, end - base,
-					       nid, flags);
+
+		if (type->cnt == type->max) {
+			if (memblock_double_array(type, obase, size))
+				return -ENOMEM;
+			else if (!use_slab && type == &memblock.reserved)
+				return memblock_reserve(obase, size);
  		}
-	}
 
-	if (!nr_new)
-		return 0;
+		if (start_rgn == -1)
+			start_rgn = idx;
+		end_rgn = idx + 1;
+		memblock_insert_region(type, idx, base, end - base,
+				       nid, flags);
+	}
 
-	/*
-	 * If this was the first round, resize array and repeat for actual
-	 * insertions; otherwise, merge and return.
-	 */
-	if (!insert) {
-		while (type->cnt + nr_new > type->max)
-			if (memblock_double_array(type, obase, size) < 0)
-				return -ENOMEM;
-		insert = true;
-		goto repeat;
-	} else {
+	if (ocnt != type->cnt)
  		memblock_merge_regions(type, start_rgn, end_rgn);
-		return 0;
-	}
+
+	return 0;
  }
 
  /**
Signature · 1 line
2.25.1
maintainer
#3 lore raw
Quoted 11 lines · Yajun Deng
Quoted 2 lines · Mike Rapoport

I don't see this micro-optimization is worth the churn and potential bugs. NAK.

There are many handouts that tell people it needs to run twice in memblock_add_range().

I think it's time to change this. I'm trying to tell people that running twice is unnecessary.

It might be unnecessary, but it's still simpler than the solutions you proposed. And, again, removing the second loop is not worth the churn and potential bugs.

Signature · 2 lines
Sincerely yours,
Mike.
author
#4 lore raw
Quoted 5 lines · Mike Rapoport
Quoted 4 lines · Yajun Deng
Quoted 2 lines · Mike Rapoport

I don't see this micro-optimization is worth the churn and potential bugs. NAK.

Quoted 9 lines
Quoted 5 lines

There are many handouts that tell people it needs to run twice in memblock_add_range().

I think it's time to change this. I'm trying to tell people that running twice is unnecessary.

It might be unnecessary, but it's still simpler than the solutions you proposed. And, again, removing the second loop is not worth the churn and potential bugs.

Okay, I got it. Thanks.