question about hand-over-hand fine-grained locking mechanism

[e0ne199]

hello everyone...probably this is my first post here so CMIIW...btw currently I have a problem regarding locking implementation on sorted singly-linked list. So far I am only able to implement coarse-locking method with mutex, and the code is as follows :

 void insert(T v) {
 /* first find position */
 std::lock_guard<std::mutex> lock(mtx);
 node<T>* pred = nullptr;
 node<T>* succ = first;
 while(succ != nullptr && succ->value < v) {
	pred = succ;
	succ = succ->next;
			}
			
  /* construct new node */
  node<T>* current = new node<T>();
  current->value = v;

  /* insert new node between pred and succ */
  current->next = succ;
  if(pred == nullptr) {
    first = current;
    } else {
     pred->next = current;
   }
}

void remove(T v) {
/* first find position */
std::lock_guard<std::mutex> lock(mtx);
node<T>* pred = nullptr;
node<T>* current = first;
while(current != nullptr && current->value < v) {
	pred = current;
	current = current->next;
   }
if(current == nullptr || current->value != v) {
        /* v not found */
	return;
   }
/* remove current */
if(pred == nullptr) {
        first = current->next;
	} else {
	pred->next = current->next;
	}
delete current;
}

do you know how to implement this code using fine-grained locking mechanism with mutex locks?? any response is very appreciated, thx

[e0ne199]

here is my attempt to use fine-grained lock with mutex, but it throws segmentation fault :

 
void insert(T v) {
    node<T>* pred = nullptr;
    node<T>* succ = first;
    
    std::unique_lock<std::mutex> currentLock(succ->mtx);
    while (succ != nullptr && succ->value < v) {
        if (pred != nullptr) {
            pred->mtx.unlock(); // Unlock the previous node
        }
        pred = succ;
        succ = succ->next;
        if (succ != nullptr) {
            currentLock = std::unique_lock<std::mutex>(succ->mtx); // Lock the next node
        }
    }

    node<T>* current = new node<T>();
    current->value = v;
    current->next = succ;

    if (pred == nullptr) {
        first = current;
    } else {
        pred->next = current;
        pred->mtx.unlock(); // Unlock the previous node
    }
    currentLock.unlock();
}

void remove(T v) {
    node<T>* pred = nullptr;
    node<T>* current = first;

    std::unique_lock<std::mutex> currentLock(current->mtx);
    while (current != nullptr && current->value < v) {
        if (pred != nullptr) {
            pred->mtx.unlock(); // Unlock the previous node
        }
        pred = current;
        current = current->next;
        if (current != nullptr) {
            currentLock = std::unique_lock<std::mutex>(current->mtx); // Lock the next node
        }
    }

    if (current == nullptr || current->value != v) {
        // v not found
        if (pred != nullptr) {
            pred->mtx.unlock(); // Unlock the previous node
        }
        return;
    }

    if (pred == nullptr) {
        first = current->next;
    } else {
        pred->next = current->next;
        pred->mtx.unlock(); // Unlock the previous node
    }

    currentLock.unlock(); // Unlock the current node
    delete current;
}

[Peter87]

std::unique_lock<Mutex>::unlock

The mutex must be locked by the current thread of execution, otherwise, the behavior is undefined.

https://en.cppreference.com/w/cpp/thread/mutex/unlock

Are you sure pred->mtx is locked when you call unlock() on line 9?

Note that operator= of std::unique_lock will unlock the mutex that it had locked before. In other words, it looks like line 14 will essentially unlock pred->mtx.

[e0ne199]

I have made several changes but I am still facing segmentation fault, the change can be seen below..correct me if I am wrong

void insert(T v) {
		
			/* first find position */
			node<T>* pred = nullptr;
			node<T>* succ = first;
			std::unique_lock<std::mutex> predlck(pred->mtx,std::defer_lock);
			std::unique_lock<std::mutex> succlck(succ->mtx,std::defer_lock);
			while(succ != nullptr && succ->value < v) {
				//predlck.lock();
				pred = succ;
				//predlck.unlock();
				succlck.lock();
				succ = succ->next;
				succlck.unlock();
			}
			
			/* construct new node */
		
			node<T>* current = new node<T>();
            std::unique_lock<std::mutex> currentlck(current->mtx,std::defer_lock);
			currentlck.lock();
			
			current->value = v;
	
			/* insert new node between pred and succ */
			
			current->next = succ;
			currentlck.unlock();
			
			if(pred == nullptr) {
				
				first = current;
			} else {
				//predlck.lock();
				pred->next = current;
				//predlck.unlock();
			}
			
		}

		void remove(T v) {
			
			/* first find position */
			node<T>* pred = nullptr;
			node<T>* current = first;
			std::unique_lock<std::mutex> predlck(pred->mtx,std::defer_lock);
			std::unique_lock<std::mutex> currentlck(current->mtx,std::defer_lock);

			while(current != nullptr && current->value < v) {
				predlck.lock();
				pred = current;
				predlck.unlock();
				currentlck.lock();
				current = current->next;
				currentlck.unlock();
			}

[Peter87]

Note that access to first also needs to be protected. This was an issue already with your previous code.

It's not only the write accesses that need to be protected. If a value can be modified then you also need to protect the reads so that you don't end up in a situation where one thread modifies the value while other threads are reading it.

[seeplus]

L6. You are de-referencing a nullptr pred!

[e0ne199]

@Peter87 do you have any suggestion or correction regarding my lock impelementation other than "first" value?

[e0ne199]

@seeplus which one?

[seeplus]

Consider L4 (pred = nullptr) and L6 (pred->mtx).

Also if first is nullptr (so succ is nullptr L5), then there is the same issue on L7

[salem c]

    node<T>* succ = first;
    std::unique_lock<std::mutex> currentLock(succ->mtx);

Between the assignment and the lock, an asynchronous process could have removed the node from the list entirely.

[e0ne199]

@seeplus could you perhaps give me a pointer about what to do with lines you just mentioned? I am sorry but C/C++ is not my strong point..

@salem c could you give me a clue about what to change on my code based on your suggestion?

[salem c]

My first thought would be why you need fine-grained locking when a global lock on the whole list is simple and effective.

    L1 *curr = head;
    while ( curr && curr->value < value ) {
        curr = curr->next;
    }

This is like 10 instructions.

    L2 *curr = head;
    std::unique_lock<std::mutex> currentLock(curr->mtx);
    while ( curr && curr->value < value ) {
        curr = curr->next;
        currentLock = std::unique_lock<std::mutex>(curr->mtx);
    }

This is hundreds - I lost the will to carry on counting.
And that's before adding the extra work to make the transition from one node to the next safe.

Even if it can be made to work, it will perform poorly.

[seeplus]

    node<T>* succ = first;
    std::unique_lock<std::mutex> currentLock(succ->mtx);

Between the assignment and the lock, an asynchronous process could have removed the node from the list entirely.

Yes - but isn't it worse than that as the value of first could change after it's value is obtained but before it is assigned to succ as the assignment is not atomic. Don't you first need a lock on first and then assign to succ?