Subversion Repositories HelenOS

Rev

Rev 2430 | 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;