Rev 2430 | Go to most recent revision | Only display areas with differences | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 2430 | Rev 2456 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | * Copyright (c) 2007 Jan Hudecek |
2 | * Copyright (c) 2007 Jan Hudecek |
3 | * Copyright (c) 2005 Jakub Jermar |
3 | * Copyright (c) 2005 Jakub Jermar |
4 | * All rights reserved. |
4 | * All rights reserved. |
5 | * |
5 | * |
6 | * Redistribution and use in source and binary forms, with or without |
6 | * Redistribution and use in source and binary forms, with or without |
7 | * modification, are permitted provided that the following conditions |
7 | * modification, are permitted provided that the following conditions |
8 | * are met: |
8 | * are met: |
9 | * |
9 | * |
10 | * - Redistributions of source code must retain the above copyright |
10 | * - Redistributions of source code must retain the above copyright |
11 | * notice, this list of conditions and the following disclaimer. |
11 | * notice, this list of conditions and the following disclaimer. |
12 | * - Redistributions in binary form must reproduce the above copyright |
12 | * - Redistributions in binary form must reproduce the above copyright |
13 | * notice, this list of conditions and the following disclaimer in the |
13 | * notice, this list of conditions and the following disclaimer in the |
14 | * documentation and/or other materials provided with the distribution. |
14 | * documentation and/or other materials provided with the distribution. |
15 | * - The name of the author may not be used to endorse or promote products |
15 | * - The name of the author may not be used to endorse or promote products |
16 | * derived from this software without specific prior written permission. |
16 | * derived from this software without specific prior written permission. |
17 | * |
17 | * |
18 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
18 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
19 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
19 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
20 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
20 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
21 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
21 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
22 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
22 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
23 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
24 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
25 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
26 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
26 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
27 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
28 | */ |
28 | */ |
29 | 29 | ||
30 | 30 | ||
31 | /* This is RCU thorough test. It should provide basic guidelines on how to use |
31 | /* This is RCU thorough test. It should provide basic guidelines on how to use |
32 | this implementation of RCU */ |
32 | this implementation of RCU */ |
33 | 33 | ||
34 | #include <synch/rcu.h> |
34 | #include <synch/rcu.h> |
35 | #include <print.h> |
35 | #include <print.h> |
36 | #include <test.h> |
36 | #include <test.h> |
37 | #include <arch/types.h> |
37 | #include <arch/types.h> |
38 | #include <proc/tasklet.h> |
38 | #include <proc/tasklet.h> |
39 | #include <arch/barrier.h> |
39 | #include <arch/barrier.h> |
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 |
51 | 51 | ||
52 | //shared flag specifying whether we should be quiet |
52 | //shared flag specifying whether we should be quiet |
53 | bool gquiet; |
53 | bool gquiet; |
54 | //count of finished threads |
54 | //count of finished threads |
55 | volatile int cfinished; |
55 | volatile int cfinished; |
56 | //the list we will manage with RCU |
56 | //the list we will manage with RCU |
57 | typedef struct data_struc { |
57 | typedef struct data_struc { |
58 | int number; |
58 | int number; |
59 | struct data_struc* next; |
59 | struct data_struc* next; |
60 | } data_t; |
60 | } data_t; |
61 | 61 | ||
62 | data_t* first; |
62 | data_t* first; |
63 | SPINLOCK_INITIALIZE(write_lock); |
63 | SPINLOCK_INITIALIZE(write_lock); |
64 | 64 | ||
65 | 65 | ||
66 | /** this thread will try to read from the list */ |
66 | /** this thread will try to read from the list */ |
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 |
141 | spinlock_lock(&write_lock); |
139 | spinlock_lock(&write_lock); |
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; |
165 | data_t* cur, *oldata; |
165 | data_t* cur, *oldata; |
166 | int i; |
166 | int i; |
167 | thread_t* t; |
167 | thread_t* t; |
168 | 168 | ||
169 | //allocate and initialize the list |
169 | //allocate and initialize the list |
170 | first = malloc(sizeof(data_t),0); |
170 | first = malloc(sizeof(data_t),0); |
171 | first->number = 0; |
171 | first->number = 0; |
172 | cur = first; |
172 | cur = first; |
173 | for (i=1;i<RCU_MAX_I;i++) { |
173 | for (i=1;i<RCU_MAX_I;i++) { |
174 | cur->next = malloc(sizeof(data_t),0); |
174 | cur->next = malloc(sizeof(data_t),0); |
175 | cur = cur->next; |
175 | cur = cur->next; |
176 | cur->number = i; |
176 | cur->number = i; |
177 | } |
177 | } |
178 | cur->next = NULL; |
178 | cur->next = NULL; |
179 | 179 | ||
180 | //initialize the counter of finished threads |
180 | //initialize the counter of finished threads |
181 | cfinished=0; |
181 | cfinished=0; |
182 | 182 | ||
183 | //start the writers |
183 | //start the writers |
184 | for(i = 0; i< WRITER_THREADS; i++) { |
184 | for(i = 0; i< WRITER_THREADS; i++) { |
185 | t=thread_create(writer,NULL, TASK, 0, "writerthread", false ); |
185 | t=thread_create(writer,NULL, TASK, 0, "writerthread", false ); |
186 | if (t != NULL) |
186 | if (t != NULL) |
187 | thread_ready(t); |
187 | thread_ready(t); |
188 | } |
188 | } |
189 | 189 | ||
190 | //start the readers |
190 | //start the readers |
191 | for(i = 0; i< READER_THREADS; i++) { |
191 | for(i = 0; i< READER_THREADS; i++) { |
192 | t=thread_create(reader,NULL, TASK, 0, "readerthread", false ); |
192 | t=thread_create(reader,NULL, TASK, 0, "readerthread", false ); |
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; |
204 | } |
205 | } |
205 | free(first); |
206 | free(first); |
206 | return NULL; |
207 | return NULL; |
207 | 208 | ||
208 | } |
209 | } |
209 | 210 | ||
210 | 211 | ||
211 | 212 |