WebSVN – HelenOS – Diff – /branches/rcu/kernel/test/synch/rcu1.c


/*
 * Copyright (c) 2007 Jan Hudecek
 * Copyright (c) 2005 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 
/* This is RCU thorough test. It should provide basic guidelines on how to use
this implementation of RCU */
 
#include <synch/rcu.h>
#include <print.h>
#include <test.h>
#include <arch/types.h>
#include <proc/tasklet.h>
#include <arch/barrier.h>
#include <arch.h>
#include <preemption.h>
#include <proc/thread.h>
 
//number of nodes in the list. The sum of the list will grow up to RCU_MAX_I^2
#define RCU_MAX_I 5000
//number of reader and writer threads in the test
#define READER_THREADS 10
#define WRITER_THREADS 10
//a sleep separates iterations of reading 
#define THREADS_SLEEP_LENGTH 50
 
//shared flag specifying whether we should be quiet
bool gquiet;
//count of finished threads
volatile int cfinished;
//the list we will manage with RCU
typedef struct data_struc {
    int number;
    struct data_struc* next;
} data_t;
 
data_t* first;
SPINLOCK_INITIALIZE(write_lock);
 
 
/** this thread will try to read from the list */
static void reader(void* a)
{
    a = (a);
    data_t* cur;
    int i = 0;
    while (true) {
 
        //entering read critical section
        rcu_read_lock();
        //proper dereferencing
        i = rcu_dereference_pointer(first).number;
        for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) {
            i += cur->number;
        }
        rcu_read_unlock();
        if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0) {
            if (!gquiet)
                printf("@");
            break;
        }
        thread_usleep(THREADS_SLEEP_LENGTH);
    }
    //we must achieve some kind of synchronization gcc wont emit inc [cfinished]
    spinlock_lock(&write_lock);
    cfinished++;
    spinlock_unlock(&write_lock);
}
 
static void writer(void* a)
{
    a = (a);
    data_t* cur;
    data_t* newdata;
    data_t* oldata;
    rcu_callback_list_t* rcudata;
    int i = 0;
    while (true) {
 
        //we must allocate the rcu structure each time, because it gets freed after the callback
        //we allocate it outside any critical section, as it could block
        rcudata = malloc(sizeof(rcu_callback_list_t),0);
        rcu_read_lock();
        i = rcu_dereference_pointer(first).number;
        for (cur = rcu_dereference_pointer(first).next; cur != NULL; cur = cur->next) {
            i += cur->number;
        }
        rcu_read_unlock();
        if (!gquiet && false)
            printf("i%d ",i);
        if (i>RCU_MAX_I*RCU_MAX_I || cfinished>0) {
            if (!gquiet)
                printf("!");
            break;
        }
 
        //insert a new member 
        newdata = malloc(sizeof(data_t),0);
        newdata->number = (i/(RCU_MAX_I/2))+1;
 
        //we have to acquire the lock for writing to the structure
        spinlock_lock(&write_lock);
        newdata->next = first;
        //rcu_assign_pointer takes care of the necessary write barriers
        rcu_assign_pointer(first, newdata);
        if (!gquiet && false)
            printf("prepending:%x,n:%d ", newdata, newdata->number);
        spinlock_unlock(&write_lock);
 
 
 
        //replace a random member
 
        //we have to lock the spinlock now, because we'll use the cur pointer later 
        //RCU doesn't provide guarantee that cur->next will point to a member of the list
        //note that read critical section DOES guarantee that the *cur will be allocated space
        //with current or past version of some member of the list
        //However, that is not sufficient as we would be changing old version, which would be freed later on
        spinlock_lock(&write_lock);
        for (cur = first; cur->next != NULL && cur->next->number >= (i/(RCU_MAX_I/2)); cur = rcu_dereference_pointer(cur).next) {
        }
        if (cur->next != NULL) {
            newdata = malloc(sizeof(data_t),0);
            //the change of number member could be done atomically, its here just to simulate some real work
            newdata->number = (i/(RCU_MAX_I/2))+10;
            newdata->next = cur->next->next;
            oldata = cur->next;
            if (!gquiet && false)
                printf("free:%x,n:%d ", cur->next, cur->next->number);
            rcu_assign_pointer(cur->next, newdata);
            //free the old member when it is safe (i.e. no references are held)
            rcu_sync_callback(&rcu_callback_free, oldata, rcudata);
            spinlock_unlock(&write_lock);
        }
 
    }
    //we must achieve some kind of synchronization gcc wont emit inc [cfinished]
    spinlock_lock(&write_lock);
    cfinished++;
    spinlock_unlock(&write_lock);
}
 
char * test_rcu1(bool quiet)
{
    gquiet = quiet;
    data_t* cur, *oldata;
    int i;
    thread_t* t;
 
    //allocate and initialize the list
    first = malloc(sizeof(data_t),0);
    first->number = 0;
    cur = first;
    for (i=1;i<RCU_MAX_I;i++) {
        cur->next = malloc(sizeof(data_t),0);
        cur = cur->next;
        cur->number = i;
    }
    cur->next = NULL;
 
    //initialize the counter of finished threads
    cfinished=0;
 
    //start the writers
    for(i = 0; i< WRITER_THREADS; i++) {
        t=thread_create(writer,NULL, TASK, 0, "writerthread", false );
        if (t != NULL)
            thread_ready(t);
    }
 
    //start the readers
    for(i = 0; i< READER_THREADS; i++) {
        t=thread_create(reader,NULL, TASK, 0, "readerthread", false );
        if (t != NULL)
            thread_ready(t);
    }
    //wait for completion
    while (cfinished<WRITER_THREADS+READER_THREADS);
    if (!gquiet)
        printf("\nfinished all threads!\n");
    //free the list
    for(cur=first->next;cur!=NULL;) {
        oldata = cur->next;
        free(cur);
        cur = oldata;
    }
    free(first);
    return NULL;
 
}
 
 
 

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

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/test/synch/rcu1.c – Rev 2430 → 2456