| Message ID | 1378894613-37279-1-git-send-email-oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa |
|---|---|
| State | Superseded |
| Headers | show |
Hi Oliver, On Wed, 11 Sep 2013, Oliver wrote: > From: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa> > > This fixes a serious bug affecting all hash types with a net element - > specifically, if a CIDR value is deleted such that none of the same size > exist any more, all larger (less-specific) values will then fail to > match. Adding back any prefix with a CIDR equal to or more specific than > the one deleted will fix it. > > Steps to reproduce: > ipset -N test hash:net > ipset -A test 1.1.0.0/16 > ipset -A test 2.2.2.0/24 > ipset -T test 1.1.1.1 #1.1.1.1 IS in set > ipset -D test 2.2.2.0/24 > ipset -T test 1.1.1.1 #1.1.1.1 IS NOT in set > > This is due to the fact that the nets counter was unconditionally > decremented prior to the iteration that shifts up the entries. Now, we > first check if there is a proceeding entry and if not, decrement it and > return. Otherwise, we proceed to iterate and then clean up the last > element afterwards. > > Signed-off-by: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa> > --- > kernel/net/netfilter/ipset/ip_set_hash_gen.h | 13 +++++++------ > 1 file changed, 7 insertions(+), 6 deletions(-) > > diff --git a/kernel/net/netfilter/ipset/ip_set_hash_gen.h b/kernel/net/netfilter/ipset/ip_set_hash_gen.h > index 7a5b776..6599ea8 100644 > --- a/kernel/net/netfilter/ipset/ip_set_hash_gen.h > +++ b/kernel/net/netfilter/ipset/ip_set_hash_gen.h > @@ -307,19 +307,20 @@ mtype_add_cidr(struct htype *h, u8 cidr, u8 nets_length, u8 n) > static void > mtype_del_cidr(struct htype *h, u8 cidr, u8 nets_length, u8 n) > { > - u8 i, j; > + u8 i, j, net_end = nets_length - 1; > > - for (i = 0; i < nets_length - 1 && h->nets[i].cidr[n] != cidr; i++) > + for (i = 0; i < net_end && h->nets[i].cidr[n] != cidr; i++) > ; > - h->nets[i].nets[n]--; > - > - if (h->nets[i].nets[n] != 0) > + if (h->nets[i].nets[n] > 1 || i == net_end || !h->nets[i + 1].nets[n]) { > + h->nets[i].nets[n]--; > return; > + } If you restored the original code in the part above, then the whole thing could be collapsed into starting the next loop from j = i + 1 (and changing the indices in the for body accordingly). > - for (j = i; j < nets_length - 1 && h->nets[j].nets[n]; j++) { > + for (j = i; j < net_end && h->nets[j].nets[n]; j++) { > h->nets[j].cidr[n] = h->nets[j + 1].cidr[n]; > h->nets[j].nets[n] = h->nets[j + 1].nets[n]; > } > + h->nets[j].nets[n] = 0; Here the checking of the value "j" is missing. > } > #endif Best regards, Jozsef - E-mail : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences H-1525 Budapest 114, POB. 49, Hungary -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wednesday 11 September 2013 16:01:18 Jozsef Kadlecsik wrote: > Hi Oliver, > > On Wed, 11 Sep 2013, Oliver wrote: > > From: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa> > > > > This fixes a serious bug affecting all hash types with a net element - > > specifically, if a CIDR value is deleted such that none of the same size > > exist any more, all larger (less-specific) values will then fail to > > match. Adding back any prefix with a CIDR equal to or more specific than > > the one deleted will fix it. > > > > Steps to reproduce: > > ipset -N test hash:net > > ipset -A test 1.1.0.0/16 > > ipset -A test 2.2.2.0/24 > > ipset -T test 1.1.1.1 #1.1.1.1 IS in set > > ipset -D test 2.2.2.0/24 > > ipset -T test 1.1.1.1 #1.1.1.1 IS NOT in set > > > > This is due to the fact that the nets counter was unconditionally > > decremented prior to the iteration that shifts up the entries. Now, we > > first check if there is a proceeding entry and if not, decrement it and > > return. Otherwise, we proceed to iterate and then clean up the last > > element afterwards. > > > > Signed-off-by: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa> > > --- > > > > kernel/net/netfilter/ipset/ip_set_hash_gen.h | 13 +++++++------ > > 1 file changed, 7 insertions(+), 6 deletions(-) > > > > diff --git a/kernel/net/netfilter/ipset/ip_set_hash_gen.h > > b/kernel/net/netfilter/ipset/ip_set_hash_gen.h index 7a5b776..6599ea8 > > 100644 > > --- a/kernel/net/netfilter/ipset/ip_set_hash_gen.h > > +++ b/kernel/net/netfilter/ipset/ip_set_hash_gen.h > > @@ -307,19 +307,20 @@ mtype_add_cidr(struct htype *h, u8 cidr, u8 > > nets_length, u8 n)> > > static void > > mtype_del_cidr(struct htype *h, u8 cidr, u8 nets_length, u8 n) > > { > > > > - u8 i, j; > > + u8 i, j, net_end = nets_length - 1; > > > > - for (i = 0; i < nets_length - 1 && h->nets[i].cidr[n] != cidr; i++) > > + for (i = 0; i < net_end && h->nets[i].cidr[n] != cidr; i++) > > > > ; > > > > - h->nets[i].nets[n]--; > > - > > - if (h->nets[i].nets[n] != 0) > > + if (h->nets[i].nets[n] > 1 || i == net_end || !h->nets[i + 1].nets[n]) { > > + h->nets[i].nets[n]--; > > > > return; > > > > + } > > If you restored the original code in the part above, then the whole thing > could be collapsed into starting the next loop from j = i + 1 (and > changing the indices in the for body accordingly). I'm not sure I follow; the whole problem is that the proceeding loop fails because the element at j gets set to zero, causing it to be skipped when we do our shift-up below - why would we want to bother with looping when we can just decrement and return immediately? > > > - for (j = i; j < nets_length - 1 && h->nets[j].nets[n]; j++) { > > + for (j = i; j < net_end && h->nets[j].nets[n]; j++) { > > > > h->nets[j].cidr[n] = h->nets[j + 1].cidr[n]; > > h->nets[j].nets[n] = h->nets[j + 1].nets[n]; > > > > } > > > > + h->nets[j].nets[n] = 0; > > Here the checking of the value "j" is missing. I suppose we can check this, but what's the point really? j is always going to be nets_length - 1, so setting that element to zero is either necessary for cleanup, or won't do anything of use (nor harm) - why add in a memory read to see if we need to do a memory write when there's no harm in just doing it regardless? Kind Regards, Oliver. -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, 11 Sep 2013, Oliver wrote: > On Wednesday 11 September 2013 16:01:18 Jozsef Kadlecsik wrote: > > > > On Wed, 11 Sep 2013, Oliver wrote: > > > From: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa> > > > > > > This fixes a serious bug affecting all hash types with a net element - > > > specifically, if a CIDR value is deleted such that none of the same size > > > exist any more, all larger (less-specific) values will then fail to > > > match. Adding back any prefix with a CIDR equal to or more specific than > > > the one deleted will fix it. > > > > > > Steps to reproduce: > > > ipset -N test hash:net > > > ipset -A test 1.1.0.0/16 > > > ipset -A test 2.2.2.0/24 > > > ipset -T test 1.1.1.1 #1.1.1.1 IS in set > > > ipset -D test 2.2.2.0/24 > > > ipset -T test 1.1.1.1 #1.1.1.1 IS NOT in set > > > > > > This is due to the fact that the nets counter was unconditionally > > > decremented prior to the iteration that shifts up the entries. Now, we > > > first check if there is a proceeding entry and if not, decrement it and > > > return. Otherwise, we proceed to iterate and then clean up the last > > > element afterwards. > > > > > > Signed-off-by: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa> > > > --- > > > > > > kernel/net/netfilter/ipset/ip_set_hash_gen.h | 13 +++++++------ > > > 1 file changed, 7 insertions(+), 6 deletions(-) > > > > > > diff --git a/kernel/net/netfilter/ipset/ip_set_hash_gen.h > > > b/kernel/net/netfilter/ipset/ip_set_hash_gen.h index 7a5b776..6599ea8 > > > 100644 > > > --- a/kernel/net/netfilter/ipset/ip_set_hash_gen.h > > > +++ b/kernel/net/netfilter/ipset/ip_set_hash_gen.h > > > @@ -307,19 +307,20 @@ mtype_add_cidr(struct htype *h, u8 cidr, u8 > > > nets_length, u8 n)> > > > static void > > > mtype_del_cidr(struct htype *h, u8 cidr, u8 nets_length, u8 n) > > > { > > > > > > - u8 i, j; > > > + u8 i, j, net_end = nets_length - 1; > > > > > > - for (i = 0; i < nets_length - 1 && h->nets[i].cidr[n] != cidr; i++) > > > + for (i = 0; i < net_end && h->nets[i].cidr[n] != cidr; i++) > > > > > > ; > > > > > > - h->nets[i].nets[n]--; > > > - > > > - if (h->nets[i].nets[n] != 0) > > > + if (h->nets[i].nets[n] > 1 || i == net_end || !h->nets[i + 1].nets[n]) > { > > > + h->nets[i].nets[n]--; > > > > > > return; > > > > > > + } > > > > If you restored the original code in the part above, then the whole thing > > could be collapsed into starting the next loop from j = i + 1 (and > > changing the indices in the for body accordingly). > > I'm not sure I follow; the whole problem is that the proceeding loop > fails because the element at j gets set to zero, causing it to be > skipped when we do our shift-up below - why would we want to bother with > looping when we can just decrement and return immediately? The for loop below would not be started due to the conditions: actually, then conditions above ("i == net_end || !h->nets[i + 1].nets[n]") would be "moved" here. In another words, would not be duplicated: for (j = i + 1; j < nets_length - 1 && h->nets[j].nets[n]; j++) h->nets[j - 1].cidr[n] = h->nets[j + 1].cidr[n]; .. } if (j < nets_length) h->nets[j - 1].nets[n] = 0; > > > - for (j = i; j < nets_length - 1 && h->nets[j].nets[n]; j++) { > > > + for (j = i; j < net_end && h->nets[j].nets[n]; j++) { > > > > > > h->nets[j].cidr[n] = h->nets[j + 1].cidr[n]; > > > h->nets[j].nets[n] = h->nets[j + 1].nets[n]; > > > > > > } > > > > > > + h->nets[j].nets[n] = 0; > > > > Here the checking of the value "j" is missing. > > I suppose we can check this, but what's the point really? j is always > going to be nets_length - 1, so setting that element to zero is either > necessary for cleanup, or won't do anything of use (nor harm) - why add > in a memory read to see if we need to do a memory write when there's no > harm in just doing it regardless? What is the difference between the first for loop in this function and this second one, from the loop variable point of view? Or, what is the value of "j" after the for loop, if all nets[j] slots are filled up? Best regards, Jozsef - E-mail : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences H-1525 Budapest 114, POB. 49, Hungary -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wednesday 11 September 2013 21:32:26 Jozsef Kadlecsik wrote: > On Wed, 11 Sep 2013, Oliver wrote: > > On Wednesday 11 September 2013 16:01:18 Jozsef Kadlecsik wrote: > > > On Wed, 11 Sep 2013, Oliver wrote: <snip> > > > > > > If you restored the original code in the part above, then the whole > > > thing > > > could be collapsed into starting the next loop from j = i + 1 (and > > > changing the indices in the for body accordingly). > > > > I'm not sure I follow; the whole problem is that the proceeding loop > > fails because the element at j gets set to zero, causing it to be > > skipped when we do our shift-up below - why would we want to bother with > > looping when we can just decrement and return immediately? > > The for loop below would not be started due to the conditions: actually, > then conditions above ("i == net_end || !h->nets[i + 1].nets[n]") would be > "moved" here. In another words, would not be duplicated: > > for (j = i + 1; j < nets_length - 1 && h->nets[j].nets[n]; j++) > h->nets[j - 1].cidr[n] = h->nets[j + 1].cidr[n]; > .. > } > if (j < nets_length) > h->nets[j - 1].nets[n] = 0; > I don't really like this idea; i + 1 after the second iteration will point to whatever was shifted up, this obviously doesn't really present a problem since if the element is empty, we won't iterate any more, but I don't think it looks good for code clarity and it's just going to be a non-changing value that the processor must pointlessly compare on every iteration (first and second run notwithstanding). Checking i against net_end is not a problem either, but again, I don't see why we would want to make the processor pointlessly recompare something that is guaranteed to be true on every iteration, especially since it's not going to make the code "simpler" or easier to follow. > > > > - for (j = i; j < nets_length - 1 && h->nets[j].nets[n]; j++) { > > > > + for (j = i; j < net_end && h->nets[j].nets[n]; j++) { > > > > > > > > h->nets[j].cidr[n] = h->nets[j + 1].cidr[n]; > > > > h->nets[j].nets[n] = h->nets[j + 1].nets[n]; > > > > > > > > } > > > > > > > > + h->nets[j].nets[n] = 0; > > > > > > Here the checking of the value "j" is missing. > > > > I suppose we can check this, but what's the point really? j is always > > going to be nets_length - 1, so setting that element to zero is either > > necessary for cleanup, or won't do anything of use (nor harm) - why add > > in a memory read to see if we need to do a memory write when there's no > > harm in just doing it regardless? > > What is the difference between the first for loop in this function and > this second one, from the loop variable point of view? Or, what is the > value of "j" after the for loop, if all nets[j] slots are filled up? Sorry, I explained this inaccurately; obviously if the array is not completely filled, the last element is going to be taken care of by virtue of the fact that j+1 would have had to be zero, thereby making the unconditional write after the loop basically a do-nothing operation. However, if it was completely filled, we *do* then need to zero it since net_end would be the reason for termination of loop iteration, leaving the old "copy" of the net element right at the end. So the question is, what is faster - reading and checking if we need to write the memory location before we do so, or just unconditionally writing it? Evidently in most cases the value is most likely going to be 0 already, so is a mem write slower than a read and compare? Do we really care that much? In any case, I do see scope for redoing the flow so that we just do everything we need under the very first for loop in the function, so I'll refactor it accordingly and mail it out. But, I would prefer not to be pontificating over syntactic sugar. Anything to do with errors I'll of course happily discuss endlessly, so if you believe one still exists, no problem. My hope was to get a change in that fixes the issue with minimal reorganisation of the code flow so that anyone looking at it later on can see, relatively quickly, exactly what was done to resolve the issue - if you want to then clean up the semantics too, fine, throw that in as a separate commit - that also avoids undermining git bisect should the clean-up introduce its own errors, somehow. Kind Regards, Oliver. -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, 12 Sep 2013, Oliver wrote: > On Wednesday 11 September 2013 21:32:26 Jozsef Kadlecsik wrote: > > On Wed, 11 Sep 2013, Oliver wrote: > > > On Wednesday 11 September 2013 16:01:18 Jozsef Kadlecsik wrote: > > > > On Wed, 11 Sep 2013, Oliver wrote: > <snip> > > > > > > > > If you restored the original code in the part above, then the whole > > > > thing > > > > could be collapsed into starting the next loop from j = i + 1 (and > > > > changing the indices in the for body accordingly). > > > > > > I'm not sure I follow; the whole problem is that the proceeding loop > > > fails because the element at j gets set to zero, causing it to be > > > skipped when we do our shift-up below - why would we want to bother with > > > looping when we can just decrement and return immediately? > > > > The for loop below would not be started due to the conditions: actually, > > then conditions above ("i == net_end || !h->nets[i + 1].nets[n]") would be > > "moved" here. In another words, would not be duplicated: > > > > for (j = i + 1; j < nets_length - 1 && h->nets[j].nets[n]; j++) > > h->nets[j - 1].cidr[n] = h->nets[j + 1].cidr[n]; > > .. > > } > > if (j < nets_length) > > h->nets[j - 1].nets[n] = 0; > > > > I don't really like this idea; i + 1 after the second iteration will > point to whatever was shifted up, this obviously doesn't really present > a problem since if the element is empty, we won't iterate any more, but > I don't think it looks good for code clarity and it's just going to be a > non-changing value that the processor must pointlessly compare on every > iteration (first and second run notwithstanding). I couldn't follow your reasoning above, maybe it's just too late here. Anyway, I'd like to ask you two small modifications compared to v3 and that's all: - Change the condition of the first "if" to an inequality, with a continue statement in the if body. Thus the next lines can be shifted to the left, for better readability. - Move the "i == net_end" test to the last position, because that is the less likely case. Thanks! Best regards, Jozsef - E-mail : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences H-1525 Budapest 114, POB. 49, Hungary -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Friday 13 September 2013 22:03:36 you wrote: <snip> > > I couldn't follow your reasoning above, maybe it's just too late here. > > Anyway, I'd like to ask you two small modifications compared to v3 and > that's all: > > - Change the condition of the first "if" to an inequality, with a > continue statement in the if body. Thus the next lines can be shifted > to the left, for better readability. OK, sounds good, I assume you mean v4, since a continue would not be valid in v3. > - Move the "i == net_end" test to the last position, because that is > the less likely case. This would create an error if we reached the very last possible iteration (i.e. *i* being 1 less than nets_length) - we need to check if it is equal to net_end (i.e. nets_length - 1) in the order it is right now so that we do not attempt a memory access beyond the boundary of the array (i.e. the final [i + 1] check within the if() statement). I'll land the new patch shortly. Kind Regards, Oliver. -- To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/kernel/net/netfilter/ipset/ip_set_hash_gen.h b/kernel/net/netfilter/ipset/ip_set_hash_gen.h index 7a5b776..6599ea8 100644 --- a/kernel/net/netfilter/ipset/ip_set_hash_gen.h +++ b/kernel/net/netfilter/ipset/ip_set_hash_gen.h @@ -307,19 +307,20 @@ mtype_add_cidr(struct htype *h, u8 cidr, u8 nets_length, u8 n) static void mtype_del_cidr(struct htype *h, u8 cidr, u8 nets_length, u8 n) { - u8 i, j; + u8 i, j, net_end = nets_length - 1; - for (i = 0; i < nets_length - 1 && h->nets[i].cidr[n] != cidr; i++) + for (i = 0; i < net_end && h->nets[i].cidr[n] != cidr; i++) ; - h->nets[i].nets[n]--; - - if (h->nets[i].nets[n] != 0) + if (h->nets[i].nets[n] > 1 || i == net_end || !h->nets[i + 1].nets[n]) { + h->nets[i].nets[n]--; return; + } - for (j = i; j < nets_length - 1 && h->nets[j].nets[n]; j++) { + for (j = i; j < net_end && h->nets[j].nets[n]; j++) { h->nets[j].cidr[n] = h->nets[j + 1].cidr[n]; h->nets[j].nets[n] = h->nets[j + 1].nets[n]; } + h->nets[j].nets[n] = 0; } #endif