Subversion Repositories HelenOS

Rev

Rev 2430 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2430 Rev 2456
Line 40... Line 40...
40
#include <arch.h>
40
#include <arch.h>
41
#include <preemption.h>
41
#include <preemption.h>
42
#include <proc/thread.h>
42
#include <proc/thread.h>
43
 
43
 
44
//number of nodes in the list. The sum of the list will grow up to RCU_MAX_I^2
44
//number of nodes in the list. The sum of the list will grow up to RCU_MAX_I^2
45
#define RCU_MAX_I 500
45
#define RCU_MAX_I 5000
46
//number of reader and writer threads in the test
46
//number of reader and writer threads in the test
47
#define READER_THREADS 10
47
#define READER_THREADS 10
48
#define WRITER_THREADS 10
48
#define WRITER_THREADS 10
49
//a sleep separates iterations of reading 
49
//a sleep separates iterations of reading 
50
#define THREADS_SLEEP_LENGTH 50
50
#define THREADS_SLEEP_LENGTH 50
Line 67... Line 67...
67
static void reader(void* a)
67
static void reader(void* a)
68
{
68
{
69
    a = (a);
69
    a = (a);
70
    data_t* cur;
70
    data_t* cur;
71
    int i = 0;
71
    int i = 0;
72
    while (true)
72
    while (true) {
73
    {
-
 
74
        //entering read critical section
73
        //entering read critical section
75
        rcu_read_lock();
74
        rcu_read_lock();
76
        //proper dereferencing
75
        //proper dereferencing
77
        i = rcu_dereference_pointer(first).number;
76
        i = rcu_dereference_pointer(first).number;
78
        for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) {
77
        for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) {
79
            i += cur->number;
78
            i += cur->number;
80
        }
79
        }
81
        rcu_read_unlock();
80
        rcu_read_unlock();
82
        if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0)
81
        if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0) {
83
        {
82
            if (!gquiet)
84
            printf("@");
83
                printf("@");
85
            break;
84
            break;
86
        }
85
        }
87
        thread_usleep(THREADS_SLEEP_LENGTH);
86
        thread_usleep(THREADS_SLEEP_LENGTH);
88
    }
87
    }
-
 
88
    //we must achieve some kind of synchronization gcc wont emit inc [cfinished]
-
 
89
    spinlock_lock(&write_lock);
89
    cfinished++;
90
    cfinished++;
-
 
91
    spinlock_unlock(&write_lock);
90
}
92
}
91
 
93
 
92
static void writer(void* a)
94
static void writer(void* a)
93
{
95
{
94
    a = (a);
96
    a = (a);
95
    data_t* cur;
97
    data_t* cur;
96
    data_t* newdata;
98
    data_t* newdata;
97
    data_t* oldata;
99
    data_t* oldata;
98
    rcu_callback_list_t* rcudata;
100
    rcu_callback_list_t* rcudata;
99
    int i = 0;
101
    int i = 0;
100
    while (true)
102
    while (true) {
101
    {
-
 
102
        //we must allocate the rcu structure each time, because it gets freed after the callback
103
        //we must allocate the rcu structure each time, because it gets freed after the callback
103
        //we allocate it outside any critical section, as it could block
104
        //we allocate it outside any critical section, as it could block
104
        rcudata = malloc(sizeof(rcu_callback_list_t),0);
105
        rcudata = malloc(sizeof(rcu_callback_list_t),0);
105
        rcu_read_lock();
106
        rcu_read_lock();
106
        i = rcu_dereference_pointer(first).number;
107
        i = rcu_dereference_pointer(first).number;
107
        for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) {
108
        for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) {
108
            i += cur->number;
109
            i += cur->number;
109
        }
110
        }
110
        rcu_read_unlock();
111
        rcu_read_unlock();
111
        if (!gquiet)
112
        if (!gquiet && false)
112
            printf("i%d ",i);
113
            printf("i%d ",i);
113
        if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0)
114
        if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0) {
114
        {
115
            if (!gquiet)
115
            printf("!");
116
                printf("!");
116
            break;
117
            break;
117
        }
118
        }
118
 
119
 
119
        //insert a new member 
120
        //insert a new member 
120
        newdata = malloc(sizeof(data_t),0);
121
        newdata = malloc(sizeof(data_t),0);
121
        newdata->number = (i/(RCU_MAX_I/2))+1;
122
        newdata->number = (i/(RCU_MAX_I/2))+1;
122
        rcu_read_lock();
-
 
123
        //we have to acquire the lock for writing to the structure
123
        //we have to acquire the lock for writing to the structure
124
        spinlock_lock(&write_lock);
124
        spinlock_lock(&write_lock);
125
        newdata->next = first;
125
        newdata->next = first;
126
        //rcu_assign_pointer takes care of the necessary write barriers
126
        //rcu_assign_pointer takes care of the necessary write barriers
127
        rcu_assign_pointer(first, newdata);
127
        rcu_assign_pointer(first, newdata);
128
        if (!gquiet)
128
        if (!gquiet && false)
129
            printf("prepending:%x,n:%d ", newdata, newdata->number);
129
            printf("prepending:%x,n:%d ", newdata, newdata->number);
130
        spinlock_unlock(&write_lock);
130
        spinlock_unlock(&write_lock);
131
        rcu_read_unlock();
-
 
132
 
131
 
133
 
132
 
134
        //replace a random member
133
        //replace a random member
135
        rcu_read_lock();
-
 
136
        //we have to lock the spinlock now, because we'll use the cur pointer later 
134
        //we have to lock the spinlock now, because we'll use the cur pointer later 
137
        //RCU doesn't provide guarantee that cur->next will point to a member of the list
135
        //RCU doesn't provide guarantee that cur->next will point to a member of the list
138
        //note that read critical section DOES guarantee that the *cur will be allocated space
136
        //note that read critical section DOES guarantee that the *cur will be allocated space
139
        //with current or past version of some member of the list
137
        //with current or past version of some member of the list
140
        //However, that is not sufficient as we would be changing old version, which would be freed later on
138
        //However, that is not sufficient as we would be changing old version, which would be freed later on
Line 142... Line 140...
142
        for (cur = first; cur->next != NULL && cur->next->number >= (i/(RCU_MAX_I/2)); cur = rcu_dereference_pointer(cur).next) {
140
        for (cur = first; cur->next != NULL && cur->next->number >= (i/(RCU_MAX_I/2)); cur = rcu_dereference_pointer(cur).next) {
143
        }
141
        }
144
        if (cur->next != NULL) {
142
        if (cur->next != NULL) {
145
            newdata = malloc(sizeof(data_t),0);
143
            newdata = malloc(sizeof(data_t),0);
146
            //the change of number member could be done atomically, its here just to simulate some real work
144
            //the change of number member could be done atomically, its here just to simulate some real work
147
            newdata->number = (i/(RCU_MAX_I/2))+5;
145
            newdata->number = (i/(RCU_MAX_I/2))+10;
148
            newdata->next = cur->next->next;
146
            newdata->next = cur->next->next;
149
            oldata = cur->next;
147
            oldata = cur->next;
150
            if (!gquiet)
148
            if (!gquiet && false)
151
                printf("free:%x,n:%d ", cur->next, cur->next->number);
149
                printf("free:%x,n:%d ", cur->next, cur->next->number);
152
            rcu_assign_pointer(cur->next, newdata);
150
            rcu_assign_pointer(cur->next, newdata);
153
            //free the old member when it is safe (i.e. no references are held)
151
            //free the old member when it is safe (i.e. no references are held)
154
            rcu_sync_callback(&rcu_callback_free, oldata, rcudata);
152
            rcu_sync_callback(&rcu_callback_free, oldata, rcudata);
155
            spinlock_unlock(&write_lock);
153
            spinlock_unlock(&write_lock);
156
        }
154
        }
157
        rcu_read_unlock(); 
-
 
158
    }
155
    }
-
 
156
    //we must achieve some kind of synchronization gcc wont emit inc [cfinished]
-
 
157
    spinlock_lock(&write_lock);
159
    cfinished++;
158
    cfinished++;
-
 
159
    spinlock_unlock(&write_lock);
160
}
160
}
161
 
161
 
162
char * test_rcu1(bool quiet)
162
char * test_rcu1(bool quiet)
163
{
163
{
164
    gquiet = quiet;
164
    gquiet = quiet;
Line 193... Line 193...
193
        if (t != NULL)
193
        if (t != NULL)
194
            thread_ready(t);
194
            thread_ready(t);
195
    }
195
    }
196
    //wait for completion
196
    //wait for completion
197
    while (cfinished<WRITER_THREADS+READER_THREADS);
197
    while (cfinished<WRITER_THREADS+READER_THREADS);
-
 
198
    if (!gquiet)
198
    printf("\nfinished all threads!\n");
199
        printf("\nfinished all threads!\n");
199
    //free the list
200
    //free the list
200
    for(cur=first->next;cur!=NULL;) {
201
    for(cur=first->next;cur!=NULL;) {
201
        oldata = cur->next;
202
        oldata = cur->next;
202
        free(cur);
203
        free(cur);
203
        cur = oldata;
204
        cur = oldata;