Listing 9.2: actual free(3) will probably cause problem
Hi Paul,
I would suggest the following patch for defer/route_refcnt.c (as in Listing 9.2). For the change in re_free, if we actually call free(3) on `rep', we will lose that piece of memory so that the READ_ONCE() at line 36 might see garbage value and will probably will not call abort(3), i.e., that is implementation specific behavior. And I don't see why will we have old <=0.
I think I understand what that code mean but you might mean some other? Hopefully I will not be too picky.
Thanks,
Yubin
----------------------------------------
CodeSamples/defer/route_refcnt.c +2 -4
@@ -36,7 +36,8 @@ DEFINE_SPINLOCK(routelock);static void re_free (struct route_entry *rep) {WRITE_ONCE (rep->re_freed,1 ); -free (rep); +/* Will not actually free it. Just use the `re_freed' as a flag */ +/*free(rep);*/ }/*
@@ -50,7 +51,6 @@ unsigned long route_lookup(unsigned long addr)struct route_entry **repp;unsigned long ret; -retry: repp = &route_list.re_next; rep =NULL ; do {
@@ -65,8 +65,6 @@ retry:if (READ_ONCE (rep->re_freed))abort (); old =atomic_read (&rep->re_refcnt); -if (old <=0 ) - goto retry; new = old +1 ; }while (atomic_cmpxchg (&rep->re_refcnt, old, new) != old);
Quoted 10 lines · Yubin Ruan
Hi Paul,
I would suggest the following patch for
defer/route_refcnt.c(as in Listing 9.2). For the change inre_free, if we actually call free(3) on `rep', we will lose that piece of memory so that theREAD_ONCE()at line 36 might see garbage value and will probably will not call abort(3), i.e., that is implementation specific behavior. And I don't see why will we haveold <=0.I think I understand what that code mean but you might mean some other? Hopefully I will not be too picky.
Yes, this code is buggy and fixing it is on my list. I would be happy to accept a patch doing a real fix, but it is not simple.
One place to start is Anthony Williams's atomic shared pointer code. The idea would be to translate that from C++ to C.
But please be aware that this is a non-trivial problem. If you try to hack together a solution, it -will- have subtle bugs. So validating your solution (even if you start from Anthony's approach) will be non-trivial. I suggest using cbmc or something similar in addition to perfbook's stress tests.
So, are you up for it? ;-)
Thanx, Paul
Quoted 40 lines
Thanks,
Yubin----------------------------------------
CodeSamples/defer/route_refcnt.c +2
-5@@ -36,7 +36,8 @@ DEFINE_SPINLOCK(routelock);static void re_free (struct route_entry *rep) {WRITE_ONCE (rep->re_freed,1 ); -free (rep); +/* Will not actually free it. Just use the `re_freed' as a flag */ +/*free(rep);*/ }/* @@ -50,7 +51,6 @@ unsigned long route_lookup(unsigned long addr)struct route_entry **repp;unsigned long ret; -retry: repp = &route_list.re_next; rep =NULL ; do {@@ -65,8 +65,6 @@ retry:if (READ_ONCE (rep->re_freed))abort (); old =atomic_read (&rep->re_refcnt); -if (old <=0 ) - goto retry; new = old +1 ; }while (atomic_cmpxchg (&rep->re_refcnt, old, new) != old); --To unsubscribe from this list: send the line "unsubscribe perfbook" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
[Off list...]
Quoted 9 lines · Paul E. McKenney
Quoted 8 lines · Yubin Ruan
Hi Paul,
I would suggest the following patch for
defer/route_refcnt.c(as in Listing 9.2). For the change inre_free, if we actually call free(3) on `rep', we will lose that piece of memory so that theREAD_ONCE()at line 36 might see garbage value and will probably will not call abort(3), i.e., that is implementation specific behavior. And I don't see why will we haveold <=0.
Quoted 8 lines
Quoted 2 lines
I think I understand what that code mean but you might mean some other? Hopefully I will not be too picky.
Yes, this code is buggy and fixing it is on my list. I would be happy to accept a patch doing a real fix, but it is not simple.
One place to start is Anthony Williams's atomic shared pointer code. The idea would be to translate that from C++ to C.
Can you provide some references?
Quoted 8 lines
But please be aware that this is a non-trivial problem. If you try to hack together a solution, it -will- have subtle bugs. So validating your solution (even if you start from Anthony's approach) will be non-trivial. I suggest using cbmc or something similar in addition to perfbook's stress tests.
So, are you up for it? ;-)
Akira, can you provide some comments? I not sure what is wrong with my suggestions.
And I currently don't know use those test. I will work on it.
Yubin
Quoted 39 lines
Quoted 38 lines
----------------------------------------
CodeSamples/defer/route_refcnt.c +2
-5@@ -36,7 +36,8 @@ DEFINE_SPINLOCK(routelock);static void re_free (struct route_entry *rep) {WRITE_ONCE (rep->re_freed,1 ); -free (rep); +/* Will not actually free it. Just use the `re_freed' as a flag */ +/*free(rep);*/ }/* @@ -50,7 +51,6 @@ unsigned long route_lookup(unsigned long addr)struct route_entry **repp;unsigned long ret; -retry: repp = &route_list.re_next; rep =NULL ; do {@@ -65,8 +65,6 @@ retry:if (READ_ONCE (rep->re_freed))abort (); old =atomic_read (&rep->re_refcnt); -if (old <=0 ) - goto retry; new = old +1 ; }while (atomic_cmpxchg (&rep->re_refcnt, old, new) != old); --To unsubscribe from this list: send the line "unsubscribe perfbook" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 1 line · Yubin Ruan
[Off list...]
Well, this was on the list. I'm keeping the CC.
Quoted 29 lines · Paul E. McKenney
Quoted 9 lines · Yubin Ruan
Quoted 8 lines
Hi Paul,
I would suggest the following patch for
defer/route_refcnt.c(as in Listing 9.2). For the change inre_free, if we actually call free(3) on `rep', we will lose that piece of memory so that theREAD_ONCE()at line 36 might see garbage value and will probably will not call abort(3), i.e., that is implementation specific behavior. And I don't see why will we haveold <=0.Quoted 8 lines
Quoted 2 lines
I think I understand what that code mean but you might mean some other? Hopefully I will not be too picky.
Yes, this code is buggy and fixing it is on my list. I would be happy to accept a patch doing a real fix, but it is not simple.
One place to start is Anthony Williams's atomic shared pointer code. The idea would be to translate that from C++ to C.
Can you provide some references?
Quoted 7 lines
But please be aware that this is a non-trivial problem. If you try to hack together a solution, it -will- have subtle bugs. So validating your solution (even if you start from Anthony's approach) will be non-trivial. I suggest using cbmc or something similar in addition to perfbook's stress tests.
Quoted 4 lines
Quoted 1 line
So, are you up for it? ;-)
Akira, can you provide some comments? I not sure what is wrong with my suggestions.
I think Paul didn't mean your suggestion was wrong. He wants formal verification of its correctness. And he might have noticed other issues in the code.
Paul, correct me if I'm guessing wrong.
Quoted 2 lines
And I currently don't know use those test. I will work on it.
The update of perfbook pushed earlier today contains relevant topics in the "formal" chapter and bibliography.
This looks to me a good opportunity for you.
Akira
Quoted 44 lines
Yubin
Quoted 39 lines
Quoted 38 lines
----------------------------------------
CodeSamples/defer/route_refcnt.c +2
-5@@ -36,7 +36,8 @@ DEFINE_SPINLOCK(routelock);static void re_free (struct route_entry *rep) {WRITE_ONCE (rep->re_freed,1 ); -free (rep); +/* Will not actually free it. Just use the `re_freed' as a flag */ +/*free(rep);*/ }/* @@ -50,7 +51,6 @@ unsigned long route_lookup(unsigned long addr)struct route_entry **repp;unsigned long ret; -retry: repp = &route_list.re_next; rep =NULL ; do {@@ -65,8 +65,6 @@ retry:if (READ_ONCE (rep->re_freed))abort (); old =atomic_read (&rep->re_refcnt); -if (old <=0 ) - goto retry; new = old +1 ; }while (atomic_cmpxchg (&rep->re_refcnt, old, new) != old); --To unsubscribe from this list: send the line "unsubscribe perfbook" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 26 lines · Akira Yokosawa
Quoted 1 line · Yubin Ruan
[Off list...]
Well, this was on the list. I'm keeping the CC.
Quoted 21 lines · Paul E. McKenney
Quoted 9 lines · Yubin Ruan
Quoted 8 lines
Hi Paul,
I would suggest the following patch for
defer/route_refcnt.c(as in Listing 9.2). For the change inre_free, if we actually call free(3) on `rep', we will lose that piece of memory so that theREAD_ONCE()at line 36 might see garbage value and will probably will not call abort(3), i.e., that is implementation specific behavior. And I don't see why will we haveold <=0.Quoted 8 lines
Quoted 2 lines
I think I understand what that code mean but you might mean some other? Hopefully I will not be too picky.
Yes, this code is buggy and fixing it is on my list. I would be happy to accept a patch doing a real fix, but it is not simple.
One place to start is Anthony Williams's atomic shared pointer code. The idea would be to translate that from C++ to C.
Can you provide some references?
https://bitbucket.org/anthonyw/atomic_shared_ptr
And, for completeness, a few others:
http://en.cppreference.com/w/cpp/experimental/atomic_shared_pt
https://isocpp.org/files/papers/N4162.pdf
Not so much a fan of this one because there really are already workloads out there that need more than 48 bits of address space, but here you go:
https://github.com/facebook/folly/blob/master/folly/concurrency/AtomicSharedPtr.h
There have been quite a few papers published on this topic over the past 20 years, most of which have at least one bug. :-/
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
But please be aware that this is a non-trivial problem. If you try to hack together a solution, it -will- have subtle bugs. So validating your solution (even if you start from Anthony's approach) will be non-trivial. I suggest using cbmc or something similar in addition to perfbook's stress tests.
So, are you up for it? ;-)
Quoted 8 lines
Quoted 2 lines
Akira, can you provide some comments? I not sure what is wrong with my suggestions.
I think Paul didn't mean your suggestion was wrong. He wants formal verification of its correctness. And he might have noticed other issues in the code.
Paul, correct me if I'm guessing wrong.
You got it -- for this level of complexity and subtlety, formal verification really is needed.
Quoted 6 lines
Quoted 1 line
And I currently don't know use those test. I will work on it.
The update of perfbook pushed earlier today contains relevant topics in the "formal" chapter and bibliography.
This looks to me a good opportunity for you.
That indeed was one of my motivations for expanding on this chapter. ;-)
I suggest starting with CBMC and Nidhugg. CBMC is easier to use, so I would start with that, but you might need Nidhugg for larger scenarios.
Thanx, Paul
Quoted 47 lines
Akira
Quoted 44 lines
Yubin
Quoted 39 lines
Quoted 38 lines
----------------------------------------
CodeSamples/defer/route_refcnt.c +2
-5@@ -36,7 +36,8 @@ DEFINE_SPINLOCK(routelock);static void re_free (struct route_entry *rep) {WRITE_ONCE (rep->re_freed,1 ); -free (rep); +/* Will not actually free it. Just use the `re_freed' as a flag */ +/*free(rep);*/ }/* @@ -50,7 +51,6 @@ unsigned long route_lookup(unsigned long addr)struct route_entry **repp;unsigned long ret; -retry: repp = &route_list.re_next; rep =NULL ; do {@@ -65,8 +65,6 @@ retry:if (READ_ONCE (rep->re_freed))abort (); old =atomic_read (&rep->re_refcnt); -if (old <=0 ) - goto retry; new = old +1 ; }while (atomic_cmpxchg (&rep->re_refcnt, old, new) != old); --To unsubscribe from this list: send the line "unsubscribe perfbook" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html