Fine grained locking in Skip List

Question

I am trying to implement lock based skiplist in c using fine grained locking mechanism. On running the code, the locking mechanism applied appears to be coarse grained. I have put locks in the preceding nodes, for insertion, using a pthread_mutex_t lock variable defined inside the node structure and releases them after usage. The whole list is not locked only the nodes are locked, still it seems to be implementing coarse grained locking mechanism. Fragment of code where the locking mechanism is done is provided below. Is the implementation wrong?

for(level = 0; valid && (level <=topLevel); level++){
            pred = preds[level];
            succ = succs[level];

            if(pred != prevPred){
                pthread_mutex_lock(pred -> lock);
                highestLocked   = level;
                prevPred        = pred;
            }

            valid = !(pred -> marked) && !(succ -> marked) && (pred -> next[level] == succ);
        }
        if(!valid){
            for(level = 0;level <= highestLocked; level++)
                pthread_mutex_unlock(preds[level] -> lock);
            continue;
        }
        newNode = createNewNode(x -> val, topLevel);
        for(level = 0; level <= topLevel; level++){
            newNode -> next[level] = succs[level];
            preds[level] -> next[level] = newNode;
        }
        newNode -> fullyLinked = 1;
        for(level = 0;level <= highestLocked; level++)
                pthread_mutex_unlock(preds[level] -> lock);

The paper followed in the coding of skiplist is by

@inproceedings{DBLP:dblp_conf/sirocco/HerlihyLLS07,
   author              = {Maurice Herlihy and 
                          Yossi Lev and 
                          Victor Luchangco and 
                          Nir Shavit},
   title               = {A Simple Optimistic Skiplist Algorithm.},
   booktitle           = {SIROCCO},
   year                = {2007},
   pages               = {124-138},
   ee                  = {http://dx.doi.org/10.1007/978-3-540-72951-8_11},
   crossref            = {2007},
}

Edit: Code for insertion of a node into skiplist

int add(Node *x, int *preval){
    int lFound, highestLocked, valid, level;
    Node *nodeFound, *pred, *succ, *prevPred, *newNode;
    // int topLevel = randomLevel(MAX_LEVEL);
    int topLevel = (rand()%MAX_LEVEL)+1;
    *preval=topLevel;
    Node **preds = (Node **)malloc(sizeof(Node *) * (MAX_LEVEL + 1));//predecessor list
    Node **succs = (Node **)malloc(sizeof(Node *) * (MAX_LEVEL + 1));//successor list
    while(1){
        lFound = find(x, preds, succs);//gets predecessor and successor list of node where x to be inserted
        if(lFound != -1){
            nodeFound = succs[lFound];
            if(!nodeFound->marked){
                while(!nodeFound->fullyLinked){;}
                return 0;
            }
            continue;
        }
        highestLocked   = -1;
        prevPred        = NULL;
        valid           = 1;
        for(level = 0; valid && (level <=topLevel); level++){
            pred = preds[level];
            succ = succs[level];
            //locking the predecessor node level
            if(pred != prevPred){
                pthread_mutex_lock(pred -> lock);
                highestLocked   = level;
                prevPred        = pred;
            }

            valid = !(pred -> marked) && !(succ -> marked) && (pred -> next[level] == succ);
        }
        //releasing locked nodes
        if(!valid){
            for(level = 0;level <= highestLocked; level++)
                pthread_mutex_unlock(preds[level] -> lock);
            continue;
        }
        newNode = createNewNode(x -> val, topLevel);
        for(level = 0; level <= topLevel; level++){
            newNode -> next[level] = succs[level];
            preds[level] -> next[level] = newNode;
        }
        newNode -> fullyLinked = 1;
        //releasing locked nodes
        for(level = 0;level <= highestLocked; level++)
                pthread_mutex_unlock(preds[level] -> lock);
        return 1;
    }   
}

Answer 1

Think about what data is being locked by your "fine grained" locking. You are locking access to the skiplist internal lists. Accessing these lists is necessary for any thread to search through the skiplist. On your first iteration of the for loop (assuming pred != prevPred in this case), you will lock pred->lock of level 0. Thus every thread will attempt to acquire the same lock the same time through the skiplist.

I suggest looking for a copy of "The Art of Multiprocessor Programming", Chapter 14 talks about Skiplists.