c++ linked list missing nodes after allocation in multiple threads, on x64 linux; why?

Question

I've included a source code you can compile and see the problem for yourself. compile with g++ -lpthread list-memchk.cpp -o list-memchk

RUN THIS, FOR EXAMPLE, ./list-memchk 43000000 30000000 10

ive included three files, first one,

list-memchk.cpp

#include <cstdlib>
#include <iostream>
#include <pthread.h>


using namespace std;


 struct node
{
    public :
          unsigned int part1; // 4 bytes
          unsigned int part2; // 4 bytes
          node *next;         //pointer, 8 bytes on 64 bit system
      unsigned int read_part1();
 };


struct LinkedList
 {
     public:
     LinkedList();
          void insert(unsigned int data[], unsigned int data1);
          bool isEmpty() const;
          node* head;
 };

unsigned int node::read_part1() {
return part1;
}
 LinkedList::LinkedList():
 head(NULL)
{
}

bool LinkedList::isEmpty() const
{
  return (head == NULL);
}

  void LinkedList::insert(unsigned int data[], unsigned int data1)
 {



    node* oldHead = head;
    node* newHead = new node();
    newHead->part1 = data[0];
    newHead->part2 = data1;
    newHead->next = oldHead;
    head = newHead;

  }

unsigned int allocations = 300000000;
unsigned int index_size = 430000000;//index of lists, 430m,.
pthread_mutex_t mutex;
                    //will be creatad on heap
    LinkedList *list = NULL;



unsigned long node_count() {

 unsigned long numNodes = 0;


for (int i=0; i<index_size; i++)
{


  node* current = list[i].head;

// if root is null, the number of nodes is 0
if(current != NULL) {

// if root is not null, we have at least one node
    numNodes++;

// count all nodes
while(current->next != NULL) {
numNodes++;
current = current->next;
}

}

}

return numNodes;

}


#include "alloc_threads.cpp"










void start_threads(int thread_count) {

alloc_threads alloc_thr[thread_count];//thread objects
pthread_t threads[thread_count];

pthread_mutex_init(&mutex, NULL);

for (int i=0; i<thread_count; i++)
{

alloc_threads *rr;

rr = new alloc_threads(list, mutex, allocations);
alloc_thr[i] = *rr;

pthread_create(&threads[i], NULL, &alloc_threads::allocation_helper,&alloc_thr[i]);

delete rr;
}

for (int i=0; i<thread_count; i++)
pthread_join( threads[i], NULL);


}








int main(int argc, char *argv[])

{
if ( argc < 4 )
{
std::cout << "Missing paramaters. " << endl;
std::cout << "Please run me like this : <list-memchk> <index_size> <allocations_per_thread> <thread_count>" << endl;
return 1;
}


index_size = strtoul(argv[1], 0, 10);
allocations = strtoul(argv[2], 0, 10);
unsigned int thr_cnt = strtoul(argv[3], 0, 10);

LinkedList list_instance;

cout << "1 LinkedList instance takes [" << sizeof(list_instance) << "] bytes in memory!"<< endl;

node node_instance;

cout << "1 node instance takes [" << sizeof(node_instance) <<"] bytes in memory !"<< endl;


list = new (nothrow) LinkedList[index_size];
    if (!list)
    {
        cout << "Error allocating memory" << endl;
        return 1;
    }


unsigned int some_data[] = {00, 01};
unsigned int index;





cout << "Allocating ..." << endl;
start_threads(thr_cnt);


unsigned long sk = ((allocations * sizeof(node_instance) + index_size*sizeof(list_instance))) / (1024*1024*1024);

cout << "This process *should* consume around " << sk <<" GBytes of memory, but does it ?"<< endl;

cout << "Allocating done, *check the process size* ..." << endl;


cout << "Lets count `nodes` to see how many do we have; counting, please wait ..." << endl;

cout << "We have reached [" << node_count() << "] nodes, expected [" << allocations * thr_cnt << "] nodes. You may press any number key to exit." << endl;

string s;
getline(std::cin, s);



return 0;
}

then, alloc_threads.cpp

#include "alloc_threads.h"
using namespace std;

alloc_threads::alloc_threads()
{
}

 void *alloc_threads::allocation_helper(void *context)
    {
        return ((alloc_threads *)context)->allocation();
    }

 alloc_threads::alloc_threads(LinkedList* x_list, pthread_mutex_t x_mutex, unsigned int x_allocations)


{
        list = x_list;
        mutex = x_mutex;
        allocations = x_allocations;
}

void * alloc_threads::allocation(void)
{

cout << "Thread started" << endl;
unsigned int some_data[] = {00, 01};
unsigned int index;
unsigned short inde;

LinkedList *list_instance2 = NULL;
for (int i=0; i<allocations; i++)
{

pthread_mutex_lock(&mutex);



index = rand();
inde = (unsigned short)index;
list_instance2 = &list[inde];

list_instance2->insert(some_data, some_data[1]);

pthread_mutex_unlock(&mutex);
}





cout << "Thread finished" << endl;
return 0;
}

alloc_threads::~alloc_threads()
{
}

and, finally, alloc_threads.h

class alloc_threads{
public:
    void *allocation(void);
    static void *allocation_helper(void *context);
    alloc_threads();
    alloc_threads(LinkedList *x_list, pthread_mutex_t x_mutex, unsigned int x_allocations);
    ~alloc_threads();
private:    
       pthread_mutex_t mutex;
       LinkedList* list;
       unsigned int allocations;

};

Code itself is not commented at all, but hopefully its not that hard to understand. what ive done, is im allocating memory with standard allocator in multiple concurrent threads, lets say, 10, for example. after allocation is done in all threads, im accessing each node and incrementing numNodes upon successful access. what i typically get, is numNodes value to be smaller by few/few hundred or few thousand than expected. what is wrong ? and, ive done this with two different allocators, both of them have the same behavior.

Answer 1

It seems, im using mutex the wrong way - it doesnt stop concurrent threads from writing to same memory.

The solution i found, is : defining mutex variable in list-memchk.cpp and avoid passing it to threads but using it as is.

list-memchk.cpp : replace mutex definition with this,

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER ;

remove

pthread_mutex_init(&mutex, NULL);

alloc_threads.h : remove mutex from this file;

alloc_threads.cpp : remove mutex = x_mutex;

Thats it. No more missing nodes. However, allocation speed is miserable. Looks like threads are waiting on each other to unlock mutex; cpu cores are idling and allocation takes huge amounts of time.