502692 - thread-safe lock-free sorted list

Status: RESOLVED INCOMPLETE

(Core :: XPCOM, enhancement)

Description

[Irina Calciu]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.0.11) Gecko/2009060308 Ubuntu/9.04 (jaunty) Firefox/3.0.11 GTB5
Build Identifier: 

a lock free implementation of a sorted list, needed for implementing a lock-free hashtable 

Reproducible: Always

Comment 1

[Irina Calciu]

Attachment: lock-free sorted list

Comment 2

[Ben Newman (:bnewman) (:benjamn)]

(In reply to comment #1)
> Created an attachment (id=387037) [details]
> lock-free sorted list

Is the Cell.h file used in this patch the same as the one from https://bugzilla.mozilla.org/show_bug.cgi?id=500308#c1 ?

Comment 3

[Irina Calciu]

(In reply to comment #2)
> (In reply to comment #1)
> > Created an attachment (id=387037) [details] [details]
> > lock-free sorted list
> 
> Is the Cell.h file used in this patch the same as the one from
> https://bugzilla.mozilla.org/show_bug.cgi?id=500308#c1 ?

yes

Alternatively, I could use another version of the Cell class that has a nsRefPtr<ValueType> value instead of using normal pointers in the SortedList class for the values of the cells. However, this means that all types the list will be used with should define AddRef and Release methods.

Comment 4

[Ben Newman (:bnewman) (:benjamn)]

Could you also post a citation for the paper you used, both for posterity and to refresh my memory?  I don't think fair use allows attaching the paper itself, unfortunately.

Comment 5

[Irina Calciu]

(In reply to comment #4)
> Could you also post a citation for the paper you used, both for posterity and
> to refresh my memory?  I don't think fair use allows attaching the paper
> itself, unfortunately.

[1] O.Shalev, N. Shavit, "Split-Ordered Lists: Lock-Free Extensible Hash Tables", Journal of the ACM, Vol. 53, No. 3, 2006, 379-405

[2] M. Michael, "High Performance Dynamic Lock-free Hash Tables and List-based Sets", In Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures, 2002, 73-82

Comment 6

[Ben Newman (:bnewman) (:benjamn)]

Comment on attachment 387037 [details] [diff] [review]
lock-free sorted list

I'm a little uneasy about using ValueType*s and NULL to mark removal.  Right now I'm trying to wrap my head around the following use of CompareAndSwap:

>+    if (!find(key, pkey, current, prev)) return PR_FALSE;
>+    if (!CompareAndSwap/*Wrapper<ValueType>*/(&(current->value), pkey, (ValueType *)NULL))

Is it actually possible for *current->value to differ from pkey between a successful find and CompareAndSwap?  In other words, under what circumstances might this CompareAndSwap return PR_FALSE?  The only other ...->value modifications are performed for newly created nodes, unless I'm missing something.

Comment 7

[Irina Calciu]

(In reply to comment #6)
> (From update of attachment 387037 [details] [diff] [review])
> I'm a little uneasy about using ValueType*s and NULL to mark removal.  Right
> now I'm trying to wrap my head around the following use of CompareAndSwap:
> 
> >+    if (!find(key, pkey, current, prev)) return PR_FALSE;
> >+    if (!CompareAndSwap/*Wrapper<ValueType>*/(&(current->value), pkey, (ValueType *)NULL))
> 
> Is it actually possible for *current->value to differ from pkey between a
> successful find and CompareAndSwap?  In other words, under what circumstances
> might this CompareAndSwap return PR_FALSE?  The only other ...->value
> modifications are performed for newly created nodes, unless I'm missing
> something.


CompareAndSwap will return false if the node has already been marked for deletion by another thread after find returns.

Comment 8

[Ben Newman (:bnewman) (:benjamn)]

(In reply to comment #7)
> CompareAndSwap will return false if the node has already been marked for
> deletion by another thread after find returns.

Ah, so the reason for this CompareAndSwap is to prevent double-frees of pkey?  I'm hoping to find a way to separate the marker from the value, for instance by storing nsRefPtr<Cell<Holder<ValueType> > >s, where Holder is a struct with a ValueType field and some sort of mMarked flag.  If Holder had a method that set mMarked and returned PR_TRUE iff it hadn't been set before, that would be enough, right?

On the other hand, I would really like to see a solution that avoids the allocation of new ValueType structures, perhaps by assuming the client will supply a copy-constructible ValueType (i.e., insert would take a const ValueType& that could just be assigned into the value field of the Holder structure).  That would eliminate the need to free pkey, and thus eliminate the risk of freeing it more than once, I think.

Comment 9

[Irina Calciu]

(In reply to comment #8)
> (In reply to comment #7)
> > CompareAndSwap will return false if the node has already been marked for
> > deletion by another thread after find returns.
> 
> Ah, so the reason for this CompareAndSwap is to prevent double-frees of pkey? 
> I'm hoping to find a way to separate the marker from the value, for instance by
> storing nsRefPtr<Cell<Holder<ValueType> > >s, where Holder is a struct with a
> ValueType field and some sort of mMarked flag.  If Holder had a method that set
> mMarked and returned PR_TRUE iff it hadn't been set before, that would be
> enough, right?
> 
> On the other hand, I would really like to see a solution that avoids the
> allocation of new ValueType structures, perhaps by assuming the client will
> supply a copy-constructible ValueType (i.e., insert would take a const
> ValueType& that could just be assigned into the value field of the Holder
> structure).  That would eliminate the need to free pkey, and thus eliminate the
> risk of freeing it more than once, I think.

OK, I changed the deletion marker to be a field in the Cell class and made value hold a copy of the key instead of a pointer. I'll upload the new version after some more testing.

Comment 10

[Irina Calciu]

Attachment: lock-free sorted list with the changes in comments 8-9

Comment 11

[Ben Newman (:bnewman) (:benjamn)]

For what it's worth, we do have a cross-platform PR_AtomicSet, which should be sufficient here (it returns the old value, so you can check to make sure it was 0):
http://mxr.mozilla.org/mozilla-central/source/nsprpub/pr/include/pratom.h#73

Comment 12

[Ben Newman (:bnewman) (:benjamn)]

(In reply to comment #11)
> which should be
> sufficient here

That is, for the purpose of marking. Still need CompareAndSwap elsewhere, of course!

Comment 13

[Irina Calciu]

Attachment: lock-free sorted list using PR_AtomicSet

Comment 14

[Ben Newman (:bnewman) (:benjamn)]

Attachment: style cleanup, small bugfixes

This patch is meant to be applied on top of the previous attachment.

I'll post an explanation for each of these changes in a followup comment.

Comment 15

[Ben Newman (:bnewman) (:benjamn)]

Comment on attachment 387985 [details] [diff] [review]
style cleanup, small bugfixes

>diff --git a/xpcom/tests/MarkCell.h b/xpcom/tests/MarkCell.h
>--- a/xpcom/tests/MarkCell.h
>+++ b/xpcom/tests/MarkCell.h
>@@ -6,32 +6,47 @@
>  */
> 
> #ifndef MARKCELL_H_
> #define MARKCELL_H_
> 
> #include "nsAutoPtr.h"
> #include "nsISupportsImpl.h"
> #include "nsCOMPtr.h"
>+#include "atomicUtil.h"
> 
>+template <typename ValueType>
>+class MarkCell {

I want these data members to be private, because I want to have some control over how they're used.  Most of the other changes to this class can be understood as accommodating this privatization (and granting minimal access to these members, as necessary).

>+  nsAutoRefCnt mRefCnt;
>+  ValueType mValue;
>+  nsRefPtr<MarkCell> mNext;
>+  PRInt32 mMark;
> 
>-template <class ValueType>
>-class MarkCell {
> public:
>-	ValueType value;
>-	int mark;
>-	nsRefPtr<MarkCell<ValueType> >  next;

MarkCell should be responsible for initializing its own data members.  Initialization lists are a nice way to do this.

>+  MarkCell() : mValue(), mMark(0) {}
>+  MarkCell(const ValueType& value) : mValue(value), mMark(0) {}

These two constructors (above and below) could be unified, come to think of it.  Just get rid of the previous constructor and make the next parameter of the constructor below default to NULL.

>+  MarkCell(const ValueType& value, MarkCell* next)
>+    : mValue(value), mNext(next), mMark(0)
>+  {}
> 
>-	nsAutoRefCnt mRefCnt;
>-	nsrefcnt AddRef();
>-	nsrefcnt Release();
>-	MarkCell(){};
>-	virtual ~MarkCell(){};

Let me apologize in advance for this next change.  You had no reason to know this NS_IMETHOD_(...) thing was necessary, so just be glad I'm here to catch things like this.  Technically it's because the NS_IMPL_THREADSAFE_* macros define the AddRef and Release methods with an __stdcall calling convention... but only on Win32.  So you'd get compiler errors when you tried to compile on Windows, which would be irritating.

>+  NS_IMETHOD_(nsrefcnt) AddRef();
>+  NS_IMETHOD_(nsrefcnt) Release();

GetValue enforces that we never change the value after constructing the cell (the ValueType& is const, and there's no SetValue method).

>+  const ValueType& GetValue() const { return mValue; }

This interface hides the actual type of mMark (PR_AtomicSet wants PRInt32) and guarantees that the value of mMark transitions only from 0 to 1.

>+  PRBool Mark() { return PR_AtomicSet(&mMark, 1) == 0; }
>+  PRBool IsMarked() const { return mMark > 0; }

The Next method allows us to retrieve the value of the next pointer but does not allow us to change the address.

>+  MarkCell* Next() { return mNext; }

For these method names, I adopted the "swing" jargon from the research literature.  The Swing method is now the only place that CompareAndSwapWrapper is called.

>+  PRBool SwingNext(MarkCell* that) { return Swing(that, that->mNext); }
>+  PRBool Swing(MarkCell* from, MarkCell* to) {

The getter_AddRefs constructor makes an object that can be safely converted to a MarkCell**.  More on this below.

>+    return CompareAndSwapWrapper<MarkCell>(getter_AddRefs(mNext), from, to);
>+  }
>+

Making the destructor protected ensures that this object is only ever destroyed by the Release method.

>+protected:
>+  virtual ~MarkCell() {};
> };
> 

Since AddRef and Release are template methods, there's no need for the inline keyword.  The inline keyword is just a hack to avoid duplicate method definitions when the header file is included multiple times, given that we have to define these methods outside the class declaration.  The compiler is a bit smarter about template methods, though, so we don't need the hack.

>-template <class ValueType> inline
>+template <typename ValueType>
> NS_IMPL_THREADSAFE_ADDREF(MarkCell<ValueType>)
>-template <class ValueType> inline
>+template <typename ValueType>
> NS_IMPL_THREADSAFE_RELEASE(MarkCell<ValueType>)
> 
>-
>-
> #endif /* MARKCELL_H_ */
>diff --git a/xpcom/tests/SortedList.h b/xpcom/tests/SortedList.h
>--- a/xpcom/tests/SortedList.h
>+++ b/xpcom/tests/SortedList.h
>@@ -22,96 +22,80 @@ private:
> 
> 	PRBool find(const ValueType &key,

I thought long and hard about these nsRefPtr reference parameters, because it's unusual in Mozilla code to pass nsRefPtrs as parameters (or to use them as return types).  No other approach was any simpler or easier to reason about, though, so I'm happy with this.

> 			nsRefPtr<MarkCell<ValueType> > &current,
> 			nsRefPtr<MarkCell<ValueType> > &prev)
> 	{
> 		while (PR_TRUE)
> 		{
> 			prev = head;
>-			current = prev->next;
>+			current = prev->Next();
> 			while (PR_TRUE)
> 			{
> 				if (current == NULL) return PR_FALSE;

Making a copy of current->value is potentially wasteful, since we don't know anything about sizeof(ValueType) or ValueType's copy constructor.

>-				ValueType ckey = current->value;
>-				int cmark = current->mark;
>-				if (prev->next != current) break;
>-				if (cmark == 1)

Instead, we can just hold a reference to the value (recall that GetValue returns a const ValueType&).

>+				const ValueType &ckey = current->GetValue();
>+				if (prev->Next() != current) break;
>+				if (current->IsMarked())
> 				{

This becomes a lot easier to read, I think, when SwingNext is used instead of CompareAndSwapWrapper:

>-					if (!CompareAndSwapWrapper<MarkCell<ValueType> >(&(prev->next), current, current->next))
>+					if (!prev->SwingNext(current))
> 					{
> 						break;
> 					}
> 				}
> 				else
> 				{
>-					if (ckey >= key)
>-					{
>-						return (ckey == key);
>-					}
>-					prev = prev->next;

Following the STL, comparable elements generally only have to implement operator<.  Unfortunately C++ doesn't synthesize operator>= from operator<, even though it's almost certainly just the negation.  Let's just use < so that ValueType doesn't have to implement operator>=.

>+					if (ckey < key)
>+						prev = prev->Next();
>+					else
>+						return ckey == key;
> 				}
>-				current = current->next;
>+				current = current->Next();
> 			}
> 		}
> 	}
> 
> public:
>-
>-	SortedList()
>-	{
>-		head = new MarkCell<ValueType>();
>-		head->value = new ValueType();
>-		head->next = NULL;
>-		head->mark = 0;
>-	}
>-

These constructors are a bit simpler now that the MarkCell constructor takes more responsibility for initialization:

>+	SortedList() : head(new MarkCell<ValueType>()) {}
> 	// key is a special key used for the first node
> 	SortedList(const ValueType &key)
>-	{
>-		head = new MarkCell<ValueType>();
>-		head->value = key;
>-		head->next = NULL;
>-		head->mark = 0;
>-	}
>+	  : head(new MarkCell<ValueType>(key))
>+	{}
> 
> 	// doesn't allow duplicates
> 	PRBool insert(const ValueType &key)
> 	{

It turns out we can avoid declaring p...

>-		nsRefPtr<MarkCell<ValueType> > p = new MarkCell<ValueType>;
>-		p->value = key;
>-		p->mark = 0;
> 		PRBool inserted = PR_FALSE;
> 		while (PR_TRUE)
> 		{
> 			nsRefPtr<MarkCell<ValueType> > current, prev;
> 			if (find(key, current, prev)) return inserted;
>-			p->next = current;
>-			if (CompareAndSwapWrapper<MarkCell<ValueType> >(&(prev->next), current, p))
>-				if (prev->mark != 1)

... given that we have a MarkCell constructor that accepts a const ValueType& and a MarkCell* next pointer.  Not a huge deal, but this way we avoid an unnecessary assignment and AddRef.  If the cell isn't used, CompareAndSwapWrapper will NS_ADDREF and NS_RELEASE it, resulting in its destruction.  That's good, since it means we don't leak.

>+			if (prev->Swing(current, new MarkCell<ValueType>(key, current)))
>+			{
>+				if (!prev->IsMarked())
> 					return PR_TRUE;

Setting inserted to PR_TRUE here is a slight departure from Michael's implementation, I think.  It makes sense to me, but I'd be interested to hear your motivation.

>-				else inserted = PR_TRUE;
>+				else
>+					inserted = PR_TRUE;
>+			}
> 		}
> 	}
> 
> 	PRBool remove(const ValueType &key)
> 	{
> 		while (PR_TRUE)
> 		{
> 			nsRefPtr<MarkCell<ValueType> > current, prev;
> 			if (!find(key, current, prev))
> 			{
> 				return PR_FALSE;
> 			}
>-			int oldval = PR_AtomicSet(&(current->mark), 1);
>-			if (oldval != 0)
>+			if (!current->Mark())
> 			{
>-				return PR_FALSE;

Michael's implementation loops back around and calls find again, whereas you were just returning PR_FALSE here.  I think I agree with the Michael implementation in this case, but, again, I'm wondering what your thoughts were.

>+				continue;
> 			}
>-			if (!CompareAndSwapWrapper<MarkCell<ValueType> >(&(prev->next), current, current->next));
>+			if (!prev->SwingNext(current))
> 			{
> 				find(key);
> 			}
> 			return PR_TRUE;
> 		}
> 	}
> 
> 
> #endif /* SORTEDLIST_H_ */
>diff --git a/xpcom/tests/atomicUtil.h b/xpcom/tests/atomicUtil.h
>--- a/xpcom/tests/atomicUtil.h
>+++ b/xpcom/tests/atomicUtil.h
>@@ -7,20 +7,20 @@
> 
> #ifndef ATOMICUTIL_H_
> #define ATOMICUTIL_H_
> 
> #include "nsAutoPtr.h"
> 
> template <class T>
> static inline
>-bool CompareAndSwapWrapper(nsRefPtr<T> *addr, T *val1, T *val2)

I really don't like passing nsRefPtr<T>*s.  See below for an example of the trouble this can cause.

>+bool CompareAndSwapWrapper(T **addr, T *val1, T *val2)
> {
> 	if (val2) NS_ADDREF(val2);
>-	if (CompareAndSwap((T**)addr, val1, val2))

Casting to a T** is very risky here, and I want you to understand two things: (1) why it's wrong, and (2) why it seems to work.

As currently implemented, nsRefPtr<T> is an object with a single data member, a T* mRawPtr.  Because the T* value sits right at the beginning of the nsRefPtr<T> object record, reinterpreting the nsRefPtr<T>* as a T** just miraculously happens to work!  The crucial point is that you don't have any control over the layout of the nsRefPtr<T> object, so it's a complete stroke of luck that the address you want happens to be just where you need it to be.  If nsRefPtr had another data member before mRawPtr, casting to a T** would probably cause a crash.

If you were to use the safer static_cast<T**>(addr), which you should, the compiler would forbid this conversion, as it should.

Remember the getter_AddRefs constructor I used in MarkCell<T>::SwingNext?  It takes an nsRefPtr<T> and returns an object that can be safely converted into a T**, so it's perfect for passing an nsRefPtr<T> "by address" to a method that expects a T**.  Bear in mind that AddRef is not called when you assign into this T**, so it's still important to manage the reference count manually in this method.

>+	if (CompareAndSwap(addr, val1, val2))
> 	{
> 		if (val1) NS_RELEASE(val1);
> 		return true;
> 	}
> 	else
> 	{
> 		if (val2) NS_RELEASE(val2);
> 		return false;

Comment 16

[Irina Calciu]

(In reply to comment #15)
> (From update of attachment 387985 [details] [diff] [review])

Thanks for all the feedback!

> Setting inserted to PR_TRUE here is a slight departure from Michael's
> implementation, I think.  It makes sense to me, but I'd be interested to hear
> your motivation.
> 
> >-				else inserted = PR_TRUE;
> >+				else
> >+					inserted = PR_TRUE;
> >+			}
> > 		}
> > 	}
> > 

Michael's paper assumes that the deletion marker is one bit from the next pointer, so his implementation can check in one CompareAndSwap 
1) if the next pointer of prev still points to current
2) if the marker of prev has been set

Since we only check 1) we can end up inserting a new node after a node that has been either deleted or just marked. 
So, if the marker of prev has been set, we need to go back to the beginning of the loop and use find to check if the element has been correctly inserted. There are no duplicates, so if find returns true, then the new node has been inserted, either by the current thread or another. 

That's what I thought about when I changed that. Please let me know if you see a better solution. 

> > 	PRBool remove(const ValueType &key)
> > 	{
> > 		while (PR_TRUE)
> > 		{
> > 			nsRefPtr<MarkCell<ValueType> > current, prev;
> > 			if (!find(key, current, prev))
> > 			{
> > 				return PR_FALSE;
> > 			}
> >-			int oldval = PR_AtomicSet(&(current->mark), 1);
> >-			if (oldval != 0)
> >+			if (!current->Mark())
> > 			{
> >-				return PR_FALSE;
> 
> Michael's implementation loops back around and calls find again, whereas you
> were just returning PR_FALSE here.  I think I agree with the Michael
> implementation in this case, but, again, I'm wondering what your thoughts were.
> 
> >+				continue;
> > 			}
> >-			if (!CompareAndSwapWrapper<MarkCell<ValueType> >(&(prev->next), current, current->next));
> >+			if (!prev->SwingNext(current))
> > 			{
> > 				find(key);
> > 			}
> > 			return PR_TRUE;
> > 		}
> > 	}
> > 
> > 

If the current thread finds that the marker of the node has already been set, it means that another thread wants to delete that node and will take care of changing prev's next pointer as well. Am I missing anything here?

Comment 17

[Ben Newman (:bnewman) (:benjamn)]

(In reply to comment #16)
> If the current thread finds that the marker of the node has already been set,
> it means that another thread wants to delete that node and will take care of
> changing prev's next pointer as well. Am I missing anything here?

Okay, I agree with that.  This means, fortunately, that we no longer need the while (PR_TRUE) loop.

Comment 18

[Ben Newman (:bnewman) (:benjamn)]

Attachment: no longer using getter_AddRefs

I think this is the simplest way of addressing the nsRefPtr<T> => T** conversion issue.

Comment 19

[Ben Newman (:bnewman) (:benjamn)]

(In reply to comment #18)
> Created an attachment (id=388840) [details]
> no longer using getter_AddRefs
> 
> I think this is the simplest way of addressing the nsRefPtr<T> => T**
> conversion issue.

You can see just the changes from the previous patch here:
https://bugzilla.mozilla.org/attachment.cgi?oldid=387985&action=interdiff&newid=388840&headers=1

Comment 20

[Irina Calciu]

Attachment: sortedlist updated + revised TestSortedList

Comment 21

[Ben Newman (:bnewman) (:benjamn)]

Comment on attachment 388951 [details] [diff] [review]
sortedlist updated + revised TestSortedList

>+template <typename ValueType>
>+class MarkCell {
>+private:
>+	ValueType mValue;
>+	PRInt32 mMark;

Just MarkCell* mNext here:

>+	MarkCell<ValueType> *mNext;
>+	nsAutoRefCnt mRefCnt;
>+
>+public:

Again, since we're inside the MarkCell class definition, you can just use MarkCell* for the Swing parameters and MarkCell for the CompareAndSwapWrapper template argument.

>+	PRBool Swing(MarkCell<ValueType> *from, MarkCell<ValueType> *to)
>+	{
>+		return CompareAndSwapWrapper<MarkCell<ValueType> >(&mNext, from, to);
>+	}


Why not call find(key, current, prev) here, thereby avoiding the extra method call and variable declarations?

>+		if (!prev->SwingNext(current))
>+		{
>+			// Guarantee that the number of deleted nodes not yet removed never
>+			// exceeds the maximum number of concurrent threads operating on the
>+			// list. (Michael 2002)

That is, here:

>+			find(key);
>+		}
>+		return PR_TRUE;
>+	}
>+
>+
>+	PRBool find(const ValueType &key)
>+	{
>+		nsRefPtr<MarkCell<ValueType> >current, prev;
>+		return find(key, current, prev);
>+	}
>+


Is this patch meant to be applied on top of the queue patch?  I had some problems with the diff or atomicUtil.h, since there was already a CompareAndSwapWrapper function definition from the queue patch.

>diff --git a/xpcom/tests/atomicUtil.h b/xpcom/tests/atomicUtil.h
>--- a/xpcom/tests/atomicUtil.h
>+++ b/xpcom/tests/atomicUtil.h
>@@ -7,32 +7,49 @@
> 
> #ifndef ATOMICUTIL_H_
> #define ATOMICUTIL_H_
> 
> #include "nsAutoPtr.h"
> 
> template <class T>
> static inline
>+bool CompareAndSwapWrapper(T **addr, T *val1, T *val2)
>+{

You can use NS_IF_ADDREF instead of the if-statement:

>+	if (val2) NS_ADDREF(val2);
>+	if (CompareAndSwap(addr, val1, val2))
>+	{

NS_IF_RELEASE(val1) here:

>+		if (val1) NS_RELEASE(val1);
>+		return true;
>+	}
>+	else
>+	{

Same:

>+		if (val2) NS_RELEASE(val2);
>+		return false;
>+	}
>+}

Comment 22

[Ben Newman (:bnewman) (:benjamn)]

Comment on attachment 388951 [details] [diff] [review]
sortedlist updated + revised TestSortedList

Make this

>+			if (!p) printf("ALLOCATION FAILED\n");

    NS_ASSERTION(p, "MarkCell allocation failed in SortedList::insert");

>+int main()
>+{
>+	ScopedXPCOM xpcom("TestSortedList");
>+	if (xpcom.failed()) return 1;
>+    int rv = 0;
>+
>+    for (int i = 0; i < 100; i++)
>+    {
>+

Maybe a little more assurance that the test is going to end? ;)

    printf("Test run %d/%d...\n", i, 100);

>+    if (NS_FAILED(TestFindFalse()))
>+    	rv = 1;

It would be nice to fail faster:

    if (NS_FAILED(rv |= TestFindFalse()) ||
        NS_FAILED(rv |= TestFindTrue()) ||
        ...
        NS_FAILED(rv |= TestRemoveHalf()))
    {
        break;
    }

>+    if (NS_FAILED(TestFindTrue()))
>+    	rv = 1;
>+    if (NS_FAILED(TestInsert()))
>+        rv = 1;
>+    if (NS_FAILED(TestInsertReverseOrder()))
>+        rv = 1;
>+    if (NS_FAILED(TestRemoveEmpty()))
>+	 rv = 1;
>+    if (NS_FAILED(TestRemoveComplete()))
>+        rv = 1;
>+    if (NS_FAILED(TestRemoveHalf()))
>+        rv = 1;
>+
>+    }
>+
>+//    if (NS_FAILED(ManualTest()))
>+//       rv = 1;
>+

Make this

>+    if (!rv) printf("TestSortedList PASSED\n");

if (NS_SUCCEEDED(rv))
    passed("TestSortedList");
else
    fail("TestSortedList");

>+	return rv;
>+}

Comment 23

[Irina Calciu]

(In reply to comment #22)
> (From update of attachment 388951 [details] [diff] [review])
> Make this
> 
> >+			if (!p) printf("ALLOCATION FAILED\n");
> 
>     NS_ASSERTION(p, "MarkCell allocation failed in SortedList::insert");
> 

I used assertions in the test code. Is it OK to use it in the implementation of the queue as well? I could return PR_FALSE or something like that...


> >+int main()
> >+{
> >+	ScopedXPCOM xpcom("TestSortedList");
> >+	if (xpcom.failed()) return 1;
> >+    int rv = 0;
> >+
> >+    for (int i = 0; i < 100; i++)
> >+    {
> >+
> 
> Maybe a little more assurance that the test is going to end? ;)
> 
>     printf("Test run %d/%d...\n", i, 100);
> 

oops..sorry for that! I wanted to comment the for loop but I forgot :)
Maybe it's too long when run with the other tests?


> >+    if (NS_FAILED(TestFindFalse()))
> >+    	rv = 1;
> 
> It would be nice to fail faster:
> 
>     if (NS_FAILED(rv |= TestFindFalse()) ||
>         NS_FAILED(rv |= TestFindTrue()) ||
>         ...
>         NS_FAILED(rv |= TestRemoveHalf()))
>     {
>         break;
>     }
> 
> >+    if (NS_FAILED(TestFindTrue()))
> >+    	rv = 1;
> >+    if (NS_FAILED(TestInsert()))
> >+        rv = 1;
> >+    if (NS_FAILED(TestInsertReverseOrder()))
> >+        rv = 1;
> >+    if (NS_FAILED(TestRemoveEmpty()))
> >+	 rv = 1;
> >+    if (NS_FAILED(TestRemoveComplete()))
> >+        rv = 1;
> >+    if (NS_FAILED(TestRemoveHalf()))
> >+        rv = 1;
> >+
> >+    }
> >+
> >+//    if (NS_FAILED(ManualTest()))
> >+//       rv = 1;
> >+
> 
> Make this
> 
> >+    if (!rv) printf("TestSortedList PASSED\n");
> 
> if (NS_SUCCEEDED(rv))
>     passed("TestSortedList");
> else
>     fail("TestSortedList");
> 
> >+	return rv;
> >+}


The tests always return NS_OK. If a test fails, it will stop with an assertion.


Regarding the atomicUtil diff and the queue patch, I actually have 2 separate patches, but the common files are modified in both of them. Might this be the cause for the problem you mentioned?

Comment 24

[Ben Newman (:bnewman) (:benjamn)]

(In reply to comment #23)
> I used assertions in the test code. Is it OK to use it in the implementation of
> the queue as well? I could return PR_FALSE or something like that...

Yes, NS_ASSERTION is appropriate here.  I don't think returning PR_FALSE is reasonable, since that's supposed to indicate the element is already in the list.

> oops..sorry for that! I wanted to comment the for loop but I forgot :)
> Maybe it's too long when run with the other tests?

Yeah, if you think you can get useful results from fewer repetitions (even just one?), that would be much friendlier.

> The tests always return NS_OK. If a test fails, it will stop with an assertion.

Unfortunately NS_ASSERTION isn't fatal when it fails.  I would prefer for SortedList::compare to return an nsresult, and for the test functions to return that value.  No need to change that right away, though, since the tests work either way.

> Regarding the atomicUtil diff and the queue patch, I actually have 2 separate
> patches, but the common files are modified in both of them. Might this be the
> cause for the problem you mentioned?

Perhaps, yeah.  Not a big deal, just wanted to make sure I wasn't missing anything more important.

Comment 25

[BugBot [:suhaib / :marco/ :calixte]]

The bug assignee didn't login in Bugzilla in the last 7 months.
:overholt, could you have a look please?
For more information, please visit auto_nag documentation.