From 03c9e0f3f9c72b36b9da30ad4b6ecb055fb6adff Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Fri, 8 May 2009 14:14:30 -0400 Subject: [PATCH 01/16] Add instruction scheduling model using SSA model As promised, here is a new model :-) So far the results are very good. Basically, I model the dependencies between the instructions using a SSA assignment. It behaves a bit like a Petri network, passing tokens between the "instructions". When instructions have multiple dependencies as input, they wait for all their input tokens to be ready before they execute. It assumes we have an infinite number of registers available to hold the variables, given this is an "abstract" architecture. Signed-off-by: Mathieu Desnoyers --- .../ooomem-double-update-minimal/DEFINES | 3 + .../ooomem-double-update-minimal/Makefile | 93 ++++++ .../ooomem-double-update-minimal/mem.sh | 29 ++ .../ooomem-double-update-minimal/mem.spin | 236 ++++++++++++++++ .../read_order.ltl | 1 + .../read_order_no_rmb.define | 1 + .../read_order_no_wmb.define | 1 + .../references.txt | 7 + formal-model/ooomem-two-writes/DEFINES | 2 + formal-model/ooomem-two-writes/Makefile | 93 ++++++ formal-model/ooomem-two-writes/mem.sh | 29 ++ formal-model/ooomem-two-writes/mem.spin | 267 ++++++++++++++++++ formal-model/ooomem-two-writes/read_order.ltl | 1 + .../ooomem-two-writes/read_order.ltl.bkp | 1 + .../read_order_no_rmb.define | 1 + .../read_order_no_wmb.define | 1 + formal-model/ooomem-two-writes/references.txt | 7 + 17 files changed, 773 insertions(+) create mode 100644 formal-model/ooomem-double-update-minimal/DEFINES create mode 100644 formal-model/ooomem-double-update-minimal/Makefile create mode 100644 formal-model/ooomem-double-update-minimal/mem.sh create mode 100644 formal-model/ooomem-double-update-minimal/mem.spin create mode 100644 formal-model/ooomem-double-update-minimal/read_order.ltl create mode 100644 formal-model/ooomem-double-update-minimal/read_order_no_rmb.define create mode 100644 formal-model/ooomem-double-update-minimal/read_order_no_wmb.define create mode 100644 formal-model/ooomem-double-update-minimal/references.txt create mode 100644 formal-model/ooomem-two-writes/DEFINES create mode 100644 formal-model/ooomem-two-writes/Makefile create mode 100644 formal-model/ooomem-two-writes/mem.sh create mode 100644 formal-model/ooomem-two-writes/mem.spin create mode 100644 formal-model/ooomem-two-writes/read_order.ltl create mode 100644 formal-model/ooomem-two-writes/read_order.ltl.bkp create mode 100644 formal-model/ooomem-two-writes/read_order_no_rmb.define create mode 100644 formal-model/ooomem-two-writes/read_order_no_wmb.define create mode 100644 formal-model/ooomem-two-writes/references.txt diff --git a/formal-model/ooomem-double-update-minimal/DEFINES b/formal-model/ooomem-double-update-minimal/DEFINES new file mode 100644 index 0000000..7cf7b24 --- /dev/null +++ b/formal-model/ooomem-double-update-minimal/DEFINES @@ -0,0 +1,3 @@ +#define read_one_is_one (read_one == 1) +#define read_two_is_one (read_two == 1) +#define read_two_done (read_two != 2) diff --git a/formal-model/ooomem-double-update-minimal/Makefile b/formal-model/ooomem-double-update-minimal/Makefile new file mode 100644 index 0000000..37422b5 --- /dev/null +++ b/formal-model/ooomem-double-update-minimal/Makefile @@ -0,0 +1,93 @@ +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +# +# Copyright (C) Mathieu Desnoyers, 2009 +# +# Authors: Mathieu Desnoyers + +#CFLAGS=-DSAFETY +#CFLAGS=-DHASH64 -DREACH +CFLAGS=-DHASH64 + +#try pan -i to get the smallest trace. + +SPINFILE=mem.spin + +default: + make read_order | tee read_order.log + make read_order_no_wmb | tee read_order_no_wmb.log + make read_order_no_rmb | tee read_order_no_rmb.log + make asserts | tee asserts.log + make summary + +#show trail : spin -v -t -N pan.ltl input.spin +# after each individual make. + +summary: + @echo + @echo "Verification summary" + @grep error *.log + +asserts: clean + cat DEFINES > .input.spin + cat ${SPINFILE} >> .input.spin + rm -f .input.spin.trail + spin -a -X .input.spin + gcc -w ${CFLAGS} -DSAFETY -o pan pan.c + ./pan -v -c1 -X -m10000 -w19 + cp .input.spin $@.spin.input + -cp .input.spin.trail $@.spin.input.trail + +read_order: clean read_order_ltl run + cp .input.spin $@.spin.input + -cp .input.spin.trail $@.spin.input.trail + +read_order_no_rmb: clean read_order_ltl read_order_no_rmb_define run + cp .input.spin $@.spin.input + -cp .input.spin.trail $@.spin.input.trail + +read_order_no_rmb_define: + cp read_order_no_rmb.define .input.define + +read_order_no_wmb: clean read_order_ltl read_order_no_wmb_define run + cp .input.spin $@.spin.input + -cp .input.spin.trail $@.spin.input.trail + +read_order_no_wmb_define: + cp read_order_no_wmb.define .input.define + +read_order_ltl: + touch .input.define + cat DEFINES > pan.ltl + cat .input.define >> pan.ltl + spin -f "!(`cat read_order.ltl | grep -v ^//`)" >> pan.ltl + +run: pan + ./pan -a -v -c1 -X -m10000 -w19 + +pan: pan.c + gcc -w ${CFLAGS} -o pan pan.c + +pan.c: pan.ltl ${SPINFILE} + cat DEFINES > .input.spin + cat .input.define >> .input.spin + cat ${SPINFILE} >> .input.spin + rm -f .input.spin.trail + spin -a -X -N pan.ltl .input.spin + +.PHONY: clean default distclean summary +clean: + rm -f pan* trail.out .input.spin* *.spin.trail .input.define +distclean: + rm -f *.trail *.input *.log diff --git a/formal-model/ooomem-double-update-minimal/mem.sh b/formal-model/ooomem-double-update-minimal/mem.sh new file mode 100644 index 0000000..56e8123 --- /dev/null +++ b/formal-model/ooomem-double-update-minimal/mem.sh @@ -0,0 +1,29 @@ +#!/bin/sh +# +# Compiles and runs the urcu.spin Promela model. +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +# +# Copyright (C) IBM Corporation, 2009 +# Mathieu Desnoyers, 2009 +# +# Authors: Paul E. McKenney +# Mathieu Desnoyers + +# Basic execution, without LTL clauses. See Makefile. + +spin -a mem.spin +cc -DSAFETY -o pan pan.c +./pan -v -c1 -X -m10000000 -w21 diff --git a/formal-model/ooomem-double-update-minimal/mem.spin b/formal-model/ooomem-double-update-minimal/mem.spin new file mode 100644 index 0000000..9fc540a --- /dev/null +++ b/formal-model/ooomem-double-update-minimal/mem.spin @@ -0,0 +1,236 @@ +/* + * mem.spin: Promela code to validate memory barriers with OOO memory. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * Copyright (c) 2009 Mathieu Desnoyers + */ + +/* Promela validation variables. */ + +/* + * Produced process data flow. Updated after each instruction to show which + * variables are ready. Assigned using SSA (static single assignment) (defuse + * analysis must be done on the program to map "real" variables to single define + * followed by use). Using one-hot bit encoding per variable to save state + * space. Used as triggers to execute the instructions having those variables + * as input. + */ + +#define PRODUCE_TOKENS(state, bits) \ + state = (state) | (bits) + +/* All bits must be active to consume. All notbits must be inactive. */ +/* Consuming a token does not clear it, it just waits for it. */ +#define CONSUME_TOKENS(state, bits, notbits) \ + ((!((state) & (notbits))) && ((state) & (bits)) == (bits)) + +#define CLEAR_TOKENS(state, bits) \ + state = (state) & ~(bits) + +/* + * Bit encoding, proc_one_produced : + */ + +#define P1_PROD_NONE (1 << 0) + +#define P1_READ_ONE (1 << 1) +#define P1_RMB (1 << 2) +#define P1_READ_TWO (1 << 3) + +int proc_one_produced; + +#define P2_PROD_NONE (1 << 0) + +#define P2_WRITE_ONE (1 << 1) +#define P2_WMB (1 << 2) +#define P2_WRITE_TWO (1 << 3) + +int proc_two_produced; + +#define NR_PROCS 2 + +#define get_pid() (_pid) + +/* + * Each process have its own data in cache. Caches are randomly updated. + * smp_wmb and smp_rmb forces cache updates (write and read), wmb_mb forces + * both. + */ + +#define DECLARE_CACHED_VAR(type, x, v) \ + type mem_##x = v; \ + type cached_##x[NR_PROCS] = v; \ + bit cache_dirty_##x[NR_PROCS] = 0; + +#define IS_CACHE_DIRTY(x, id) (cache_dirty_##x[id]) + +#define READ_CACHED_VAR(x) \ + (cached_##x[get_pid()]) + +#define WRITE_CACHED_VAR(x, v) \ + atomic { \ + cached_##x[get_pid()] = v; \ + cache_dirty_##x[get_pid()] = 1; \ + } + +#define CACHE_WRITE_TO_MEM(x, id) \ + if \ + :: IS_CACHE_DIRTY(x, id) -> \ + mem_##x = cached_##x[id]; \ + cache_dirty_##x[id] = 0; \ + :: else -> \ + skip \ + fi; + +#define CACHE_READ_FROM_MEM(x, id) \ + if \ + :: !IS_CACHE_DIRTY(x, id) -> \ + cached_##x[id] = mem_##x; \ + :: else -> \ + skip \ + fi; + +/* + * May update other caches if cache is dirty, or not. + */ +#define RANDOM_CACHE_WRITE_TO_MEM(x, id) \ + if \ + :: 1 -> CACHE_WRITE_TO_MEM(x, id); \ + :: 1 -> skip \ + fi; + +#define RANDOM_CACHE_READ_FROM_MEM(x, id)\ + if \ + :: 1 -> CACHE_READ_FROM_MEM(x, id); \ + :: 1 -> skip \ + fi; + +inline ooo_mem() +{ + atomic { + RANDOM_CACHE_WRITE_TO_MEM(alpha, get_pid()); + RANDOM_CACHE_WRITE_TO_MEM(beta, get_pid()); + RANDOM_CACHE_READ_FROM_MEM(alpha, get_pid()); + RANDOM_CACHE_READ_FROM_MEM(beta, get_pid()); + } +} + +/* must consume all prior read tokens */ +inline smp_rmb() +{ + atomic { + /* todo : consume all read tokens .. ? */ + CACHE_READ_FROM_MEM(alpha, get_pid()); + CACHE_READ_FROM_MEM(beta, get_pid()); + } +} + +/* must consume all prior write tokens */ +inline smp_wmb() +{ + atomic { + CACHE_WRITE_TO_MEM(alpha, get_pid()); + CACHE_WRITE_TO_MEM(beta, get_pid()); + } +} + +/* sync_core() must consume all prior read and write tokens, including rmb/wmb + * tokens */ + +/* must consume all prior read and write tokens */ +inline smp_mb() +{ + atomic { + smp_wmb(); + /* sync_core() */ + smp_rmb(); + } +} + +/* Keep in sync manually with smp_rmb, wmp_wmb and ooo_mem */ +DECLARE_CACHED_VAR(byte, alpha, 0); +DECLARE_CACHED_VAR(byte, beta, 0); + +/* value 2 is uninitialized */ +byte read_one = 2; +byte read_two = 2; + +active proctype test_proc_one() +{ + assert(get_pid() < NR_PROCS); + + PRODUCE_TOKENS(proc_one_produced, P1_PROD_NONE); +#ifdef NO_RMB + PRODUCE_TOKENS(proc_one_produced, P1_RMB); +#endif + + do + :: CONSUME_TOKENS(proc_one_produced, P1_PROD_NONE, P1_READ_ONE) -> + ooo_mem(); + read_one = READ_CACHED_VAR(beta); + ooo_mem(); + PRODUCE_TOKENS(proc_one_produced, P1_READ_ONE); + :: CONSUME_TOKENS(proc_one_produced, P1_READ_ONE, P1_RMB) -> + smp_rmb(); + PRODUCE_TOKENS(proc_one_produced, P1_RMB); + :: CONSUME_TOKENS(proc_one_produced, P1_RMB, P1_READ_TWO) -> + ooo_mem(); + read_two = READ_CACHED_VAR(alpha); + ooo_mem(); + PRODUCE_TOKENS(proc_one_produced, P1_READ_TWO); + :: CONSUME_TOKENS(proc_one_produced, P1_PROD_NONE | P1_READ_ONE + | P1_RMB | P1_READ_TWO, 0) -> + break; + od; + + //CLEAR_TOKENS(proc_one_produced, + // P1_PROD_NONE | P1_READ_ONE | P1_RMB | P2_READ_TWO); + + // test : [] (read_one == 1 -> read_two == 1) + assert(read_one != 1 || read_two == 1); +} + +active proctype test_proc_two() +{ + assert(get_pid() < NR_PROCS); + + PRODUCE_TOKENS(proc_two_produced, P2_PROD_NONE); +#ifdef NO_WMB + PRODUCE_TOKENS(proc_two_produced, P2_WMB); +#endif + + do + :: CONSUME_TOKENS(proc_two_produced, P2_PROD_NONE, P2_WRITE_ONE) -> + ooo_mem(); + WRITE_CACHED_VAR(alpha, 1); + ooo_mem(); + PRODUCE_TOKENS(proc_two_produced, P2_WRITE_ONE); + :: CONSUME_TOKENS(proc_two_produced, P2_WRITE_ONE, P2_WMB) -> + smp_wmb(); + PRODUCE_TOKENS(proc_two_produced, P2_WMB); + :: CONSUME_TOKENS(proc_two_produced, P2_WMB, P2_WRITE_TWO) -> + ooo_mem(); + WRITE_CACHED_VAR(beta, 1); + ooo_mem(); + PRODUCE_TOKENS(proc_two_produced, P2_WRITE_TWO); + :: CONSUME_TOKENS(proc_two_produced, P2_PROD_NONE | P2_WRITE_ONE + | P2_WMB | P2_WRITE_TWO, 0) -> + break; + od; + + //CLEAR_TOKENS(proc_two_produced, + // P2_PROD_NONE | P2_WRITE_ONE | P2_WMB | P2_WRITE_TWO); +} diff --git a/formal-model/ooomem-double-update-minimal/read_order.ltl b/formal-model/ooomem-double-update-minimal/read_order.ltl new file mode 100644 index 0000000..dec26f2 --- /dev/null +++ b/formal-model/ooomem-double-update-minimal/read_order.ltl @@ -0,0 +1 @@ +[] (read_one_is_one -> (!read_two_done || read_two_is_one)) diff --git a/formal-model/ooomem-double-update-minimal/read_order_no_rmb.define b/formal-model/ooomem-double-update-minimal/read_order_no_rmb.define new file mode 100644 index 0000000..73e61a4 --- /dev/null +++ b/formal-model/ooomem-double-update-minimal/read_order_no_rmb.define @@ -0,0 +1 @@ +#define NO_RMB diff --git a/formal-model/ooomem-double-update-minimal/read_order_no_wmb.define b/formal-model/ooomem-double-update-minimal/read_order_no_wmb.define new file mode 100644 index 0000000..710f29d --- /dev/null +++ b/formal-model/ooomem-double-update-minimal/read_order_no_wmb.define @@ -0,0 +1 @@ +#define NO_WMB diff --git a/formal-model/ooomem-double-update-minimal/references.txt b/formal-model/ooomem-double-update-minimal/references.txt new file mode 100644 index 0000000..ca6798f --- /dev/null +++ b/formal-model/ooomem-double-update-minimal/references.txt @@ -0,0 +1,7 @@ +http://spinroot.com/spin/Man/ltl.html +http://en.wikipedia.org/wiki/Linear_temporal_logic +http://www.dcs.gla.ac.uk/~muffy/MRS4-2002/lect11.ppt + +http://www.lsv.ens-cachan.fr/~gastin/ltl2ba/index.php +http://spinroot.com/spin/Man/index.html +http://spinroot.com/spin/Man/promela.html diff --git a/formal-model/ooomem-two-writes/DEFINES b/formal-model/ooomem-two-writes/DEFINES new file mode 100644 index 0000000..e74150d --- /dev/null +++ b/formal-model/ooomem-two-writes/DEFINES @@ -0,0 +1,2 @@ +#define read_one_is_zero (read_one == 0) +#define read_two_is_zero (read_two == 0) diff --git a/formal-model/ooomem-two-writes/Makefile b/formal-model/ooomem-two-writes/Makefile new file mode 100644 index 0000000..37422b5 --- /dev/null +++ b/formal-model/ooomem-two-writes/Makefile @@ -0,0 +1,93 @@ +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +# +# Copyright (C) Mathieu Desnoyers, 2009 +# +# Authors: Mathieu Desnoyers + +#CFLAGS=-DSAFETY +#CFLAGS=-DHASH64 -DREACH +CFLAGS=-DHASH64 + +#try pan -i to get the smallest trace. + +SPINFILE=mem.spin + +default: + make read_order | tee read_order.log + make read_order_no_wmb | tee read_order_no_wmb.log + make read_order_no_rmb | tee read_order_no_rmb.log + make asserts | tee asserts.log + make summary + +#show trail : spin -v -t -N pan.ltl input.spin +# after each individual make. + +summary: + @echo + @echo "Verification summary" + @grep error *.log + +asserts: clean + cat DEFINES > .input.spin + cat ${SPINFILE} >> .input.spin + rm -f .input.spin.trail + spin -a -X .input.spin + gcc -w ${CFLAGS} -DSAFETY -o pan pan.c + ./pan -v -c1 -X -m10000 -w19 + cp .input.spin $@.spin.input + -cp .input.spin.trail $@.spin.input.trail + +read_order: clean read_order_ltl run + cp .input.spin $@.spin.input + -cp .input.spin.trail $@.spin.input.trail + +read_order_no_rmb: clean read_order_ltl read_order_no_rmb_define run + cp .input.spin $@.spin.input + -cp .input.spin.trail $@.spin.input.trail + +read_order_no_rmb_define: + cp read_order_no_rmb.define .input.define + +read_order_no_wmb: clean read_order_ltl read_order_no_wmb_define run + cp .input.spin $@.spin.input + -cp .input.spin.trail $@.spin.input.trail + +read_order_no_wmb_define: + cp read_order_no_wmb.define .input.define + +read_order_ltl: + touch .input.define + cat DEFINES > pan.ltl + cat .input.define >> pan.ltl + spin -f "!(`cat read_order.ltl | grep -v ^//`)" >> pan.ltl + +run: pan + ./pan -a -v -c1 -X -m10000 -w19 + +pan: pan.c + gcc -w ${CFLAGS} -o pan pan.c + +pan.c: pan.ltl ${SPINFILE} + cat DEFINES > .input.spin + cat .input.define >> .input.spin + cat ${SPINFILE} >> .input.spin + rm -f .input.spin.trail + spin -a -X -N pan.ltl .input.spin + +.PHONY: clean default distclean summary +clean: + rm -f pan* trail.out .input.spin* *.spin.trail .input.define +distclean: + rm -f *.trail *.input *.log diff --git a/formal-model/ooomem-two-writes/mem.sh b/formal-model/ooomem-two-writes/mem.sh new file mode 100644 index 0000000..56e8123 --- /dev/null +++ b/formal-model/ooomem-two-writes/mem.sh @@ -0,0 +1,29 @@ +#!/bin/sh +# +# Compiles and runs the urcu.spin Promela model. +# +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +# +# Copyright (C) IBM Corporation, 2009 +# Mathieu Desnoyers, 2009 +# +# Authors: Paul E. McKenney +# Mathieu Desnoyers + +# Basic execution, without LTL clauses. See Makefile. + +spin -a mem.spin +cc -DSAFETY -o pan pan.c +./pan -v -c1 -X -m10000000 -w21 diff --git a/formal-model/ooomem-two-writes/mem.spin b/formal-model/ooomem-two-writes/mem.spin new file mode 100644 index 0000000..4892c5e --- /dev/null +++ b/formal-model/ooomem-two-writes/mem.spin @@ -0,0 +1,267 @@ +/* + * mem.spin: Promela code to validate memory barriers with OOO memory. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * Copyright (c) 2009 Mathieu Desnoyers + */ + +/* Promela validation variables. */ + +/* + * Produced process data flow. Updated after each instruction to show which + * variables are ready. Assigned using SSA (static single assignment) (defuse + * analysis must be done on the program to map "real" variables to single define + * followed by use). Using one-hot bit encoding per variable to save state + * space. Used as triggers to execute the instructions having those variables + * as input. + */ + +#define PRODUCE_TOKENS(state, bits) \ + state = (state) | (bits) + +/* All bits must be active to consume. All notbits must be inactive. */ +/* Consuming a token does not clear it, it just waits for it. */ +#define CONSUME_TOKENS(state, bits, notbits) \ + ((!((state) & (notbits))) && ((state) & (bits)) == (bits)) + +#define CLEAR_TOKENS(state, bits) \ + state = (state) & ~(bits) + +/* + * Bit encoding, proc_one_produced : + */ + +#define P1_PROD_NONE (1 << 0) + +#define P1_WRITE (1 << 1) +#define P1_WMB (1 << 2) +#define P1_SYNC_CORE (1 << 3) +#define P1_RMB (1 << 4) +#define P1_READ (1 << 5) + +int proc_one_produced; + +#define P2_PROD_NONE (1 << 0) + +#define P2_WRITE (1 << 1) +#define P2_WMB (1 << 2) +#define P2_SYNC_CORE (1 << 3) +#define P2_RMB (1 << 4) +#define P2_READ (1 << 5) + +int proc_two_produced; + +#define NR_PROCS 2 + +#define get_pid() (_pid) + +/* + * Each process have its own data in cache. Caches are randomly updated. + * smp_wmb and smp_rmb forces cache updates (write and read), wmb_mb forces + * both. + */ + +#define DECLARE_CACHED_VAR(type, x, v) \ + type mem_##x = v; \ + type cached_##x[NR_PROCS] = v; \ + bit cache_dirty_##x[NR_PROCS] = 0; + +#define IS_CACHE_DIRTY(x, id) (cache_dirty_##x[id]) + +#define READ_CACHED_VAR(x) \ + (cached_##x[get_pid()]) + +#define WRITE_CACHED_VAR(x, v) \ + atomic { \ + cached_##x[get_pid()] = v; \ + cache_dirty_##x[get_pid()] = 1; \ + } + +#define CACHE_WRITE_TO_MEM(x, id) \ + if \ + :: IS_CACHE_DIRTY(x, id) -> \ + mem_##x = cached_##x[id]; \ + cache_dirty_##x[id] = 0; \ + :: else -> \ + skip \ + fi; + +#define CACHE_READ_FROM_MEM(x, id) \ + if \ + :: !IS_CACHE_DIRTY(x, id) -> \ + cached_##x[id] = mem_##x; \ + :: else -> \ + skip \ + fi; + +/* + * May update other caches if cache is dirty, or not. + */ +#define RANDOM_CACHE_WRITE_TO_MEM(x, id) \ + if \ + :: 1 -> CACHE_WRITE_TO_MEM(x, id); \ + :: 1 -> skip \ + fi; + +#define RANDOM_CACHE_READ_FROM_MEM(x, id)\ + if \ + :: 1 -> CACHE_READ_FROM_MEM(x, id); \ + :: 1 -> skip \ + fi; + +inline ooo_mem() +{ + atomic { + RANDOM_CACHE_WRITE_TO_MEM(alpha, get_pid()); + RANDOM_CACHE_WRITE_TO_MEM(beta, get_pid()); + RANDOM_CACHE_READ_FROM_MEM(alpha, get_pid()); + RANDOM_CACHE_READ_FROM_MEM(beta, get_pid()); + } +} + +/* must consume all prior read tokens */ +inline smp_rmb() +{ + atomic { + /* todo : consume all read tokens .. ? */ + CACHE_READ_FROM_MEM(alpha, get_pid()); + CACHE_READ_FROM_MEM(beta, get_pid()); + } +} + +/* must consume all prior write tokens */ +inline smp_wmb() +{ + atomic { + CACHE_WRITE_TO_MEM(alpha, get_pid()); + CACHE_WRITE_TO_MEM(beta, get_pid()); + } +} + +/* sync_core() must consume all prior read and write tokens, including rmb/wmb + * tokens */ + +/* must consume all prior read and write tokens */ +inline smp_mb() +{ + atomic { + smp_wmb(); + /* sync_core() */ + smp_rmb(); + } +} + +/* Keep in sync manually with smp_rmb, wmp_wmb and ooo_mem */ +DECLARE_CACHED_VAR(byte, alpha, 0); +DECLARE_CACHED_VAR(byte, beta, 0); + +/* value 2 is uninitialized */ +byte read_one = 2; +byte read_two = 2; + +active proctype test_proc_one() +{ + assert(get_pid() < NR_PROCS); + + PRODUCE_TOKENS(proc_one_produced, P1_PROD_NONE); + +#ifdef NO_WMB + PRODUCE_TOKENS(proc_one_produced, P1_WMB); +#endif +#ifdef NO_RMB + PRODUCE_TOKENS(proc_one_produced, P1_RMB); +#endif + + do + :: CONSUME_TOKENS(proc_one_produced, P1_PROD_NONE, P1_WRITE) -> + ooo_mem(); + WRITE_CACHED_VAR(alpha, 1); + ooo_mem(); + PRODUCE_TOKENS(proc_one_produced, P1_WRITE); + :: CONSUME_TOKENS(proc_one_produced, P1_WRITE, P1_WMB) -> + smp_wmb(); + PRODUCE_TOKENS(proc_one_produced, P1_WMB); + :: CONSUME_TOKENS(proc_one_produced, P1_WRITE | P1_WMB, P1_SYNC_CORE) -> + /* sync_core(); */ + PRODUCE_TOKENS(proc_one_produced, P1_SYNC_CORE); + :: CONSUME_TOKENS(proc_one_produced, P1_SYNC_CORE, P1_RMB) -> + smp_rmb(); + PRODUCE_TOKENS(proc_one_produced, P1_RMB); + :: CONSUME_TOKENS(proc_one_produced, P1_RMB | P1_SYNC_CORE, P1_READ) -> + ooo_mem(); + read_one = READ_CACHED_VAR(beta); + ooo_mem(); + PRODUCE_TOKENS(proc_one_produced, P1_READ); + :: CONSUME_TOKENS(proc_one_produced, P1_PROD_NONE | P1_WRITE + | P1_WMB | P1_SYNC_CORE | P1_RMB | P1_READ, 0) -> + break; + od; + + //CLEAR_TOKENS(proc_one_produced, + // P1_PROD_NONE | P1_WRITE | P1_WMB | P1_SYNC_CORE | P1_RMB | + // P2_READ); + + // test : [] (read_one == 0 -> read_two != 0) + // test : [] (read_two == 0 -> read_one != 0) + assert(!(read_one == 0 && read_two == 0)); +} + +active proctype test_proc_two() +{ + assert(get_pid() < NR_PROCS); + + PRODUCE_TOKENS(proc_two_produced, P2_PROD_NONE); + +#ifdef NO_WMB + PRODUCE_TOKENS(proc_two_produced, P2_WMB); +#endif +#ifdef NO_RMB + PRODUCE_TOKENS(proc_two_produced, P2_RMB); +#endif + + do + :: CONSUME_TOKENS(proc_two_produced, P2_PROD_NONE, P2_WRITE) -> + ooo_mem(); + WRITE_CACHED_VAR(beta, 1); + ooo_mem(); + PRODUCE_TOKENS(proc_two_produced, P2_WRITE); + :: CONSUME_TOKENS(proc_two_produced, P2_WRITE, P2_WMB) -> + smp_wmb(); + PRODUCE_TOKENS(proc_two_produced, P2_WMB); + :: CONSUME_TOKENS(proc_two_produced, P2_WRITE | P2_WMB, P2_SYNC_CORE) -> + /* sync_core(); */ + PRODUCE_TOKENS(proc_two_produced, P2_SYNC_CORE); + :: CONSUME_TOKENS(proc_two_produced, P2_SYNC_CORE, P2_RMB) -> + smp_rmb(); + PRODUCE_TOKENS(proc_two_produced, P2_RMB); + :: CONSUME_TOKENS(proc_two_produced, P2_SYNC_CORE | P2_RMB, P2_READ) -> + ooo_mem(); + read_two = READ_CACHED_VAR(alpha); + ooo_mem(); + PRODUCE_TOKENS(proc_two_produced, P2_READ); + :: CONSUME_TOKENS(proc_two_produced, P2_PROD_NONE | P2_WRITE + | P2_WMB | P2_SYNC_CORE | P2_RMB | P2_READ, 0) -> + break; + od; + + //CLEAR_TOKENS(proc_two_produced, + // P2_PROD_NONE | P2_WRITE | P2_WMB | P2_SYNC_CORE | P2_RMB | + // P2_READ); + + // test : [] (read_one == 0 -> read_two != 0) + // test : [] (read_two == 0 -> read_one != 0) + assert(!(read_one == 0 && read_two == 0)); +} diff --git a/formal-model/ooomem-two-writes/read_order.ltl b/formal-model/ooomem-two-writes/read_order.ltl new file mode 100644 index 0000000..f4dbf03 --- /dev/null +++ b/formal-model/ooomem-two-writes/read_order.ltl @@ -0,0 +1 @@ +[] (read_one_is_zero -> !read_two_is_zero) diff --git a/formal-model/ooomem-two-writes/read_order.ltl.bkp b/formal-model/ooomem-two-writes/read_order.ltl.bkp new file mode 100644 index 0000000..f4dbf03 --- /dev/null +++ b/formal-model/ooomem-two-writes/read_order.ltl.bkp @@ -0,0 +1 @@ +[] (read_one_is_zero -> !read_two_is_zero) diff --git a/formal-model/ooomem-two-writes/read_order_no_rmb.define b/formal-model/ooomem-two-writes/read_order_no_rmb.define new file mode 100644 index 0000000..73e61a4 --- /dev/null +++ b/formal-model/ooomem-two-writes/read_order_no_rmb.define @@ -0,0 +1 @@ +#define NO_RMB diff --git a/formal-model/ooomem-two-writes/read_order_no_wmb.define b/formal-model/ooomem-two-writes/read_order_no_wmb.define new file mode 100644 index 0000000..710f29d --- /dev/null +++ b/formal-model/ooomem-two-writes/read_order_no_wmb.define @@ -0,0 +1 @@ +#define NO_WMB diff --git a/formal-model/ooomem-two-writes/references.txt b/formal-model/ooomem-two-writes/references.txt new file mode 100644 index 0000000..ca6798f --- /dev/null +++ b/formal-model/ooomem-two-writes/references.txt @@ -0,0 +1,7 @@ +http://spinroot.com/spin/Man/ltl.html +http://en.wikipedia.org/wiki/Linear_temporal_logic +http://www.dcs.gla.ac.uk/~muffy/MRS4-2002/lect11.ppt + +http://www.lsv.ens-cachan.fr/~gastin/ltl2ba/index.php +http://spinroot.com/spin/Man/index.html +http://spinroot.com/spin/Man/promela.html -- 2.34.1 From 4b8839f157982c717e307a2045428d3582185b11 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Fri, 8 May 2009 14:18:03 -0400 Subject: [PATCH 02/16] Add no sync_core() test to ooo two writes model Signed-off-by: Mathieu Desnoyers --- formal-model/ooomem-two-writes/mem.spin | 6 ++++++ formal-model/ooomem-two-writes/read_order_no_sync.define | 1 + 2 files changed, 7 insertions(+) create mode 100644 formal-model/ooomem-two-writes/read_order_no_sync.define diff --git a/formal-model/ooomem-two-writes/mem.spin b/formal-model/ooomem-two-writes/mem.spin index 4892c5e..828ff4a 100644 --- a/formal-model/ooomem-two-writes/mem.spin +++ b/formal-model/ooomem-two-writes/mem.spin @@ -184,6 +184,9 @@ active proctype test_proc_one() #ifdef NO_RMB PRODUCE_TOKENS(proc_one_produced, P1_RMB); #endif +#ifdef NO_SYNC + PRODUCE_TOKENS(proc_one_produced, P1_SYNC_CORE); +#endif do :: CONSUME_TOKENS(proc_one_produced, P1_PROD_NONE, P1_WRITE) -> @@ -231,6 +234,9 @@ active proctype test_proc_two() #ifdef NO_RMB PRODUCE_TOKENS(proc_two_produced, P2_RMB); #endif +#ifdef NO_SYNC + PRODUCE_TOKENS(proc_two_produced, P2_SYNC_CORE); +#endif do :: CONSUME_TOKENS(proc_two_produced, P2_PROD_NONE, P2_WRITE) -> diff --git a/formal-model/ooomem-two-writes/read_order_no_sync.define b/formal-model/ooomem-two-writes/read_order_no_sync.define new file mode 100644 index 0000000..0d2f8cf --- /dev/null +++ b/formal-model/ooomem-two-writes/read_order_no_sync.define @@ -0,0 +1 @@ +#define NO_SYNC -- 2.34.1 From 3db2d75b432e617014976239f694b91de2bc0d7d Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Fri, 8 May 2009 15:54:54 -0400 Subject: [PATCH 03/16] formal verif : move bits produced declarations closer to processes Signed-off-by: Mathieu Desnoyers --- .../ooomem-double-update-minimal/mem.spin | 45 +++++++++------- formal-model/ooomem-two-writes/mem.spin | 53 ++++++++++--------- 2 files changed, 54 insertions(+), 44 deletions(-) diff --git a/formal-model/ooomem-double-update-minimal/mem.spin b/formal-model/ooomem-double-update-minimal/mem.spin index 9fc540a..bae92d6 100644 --- a/formal-model/ooomem-double-update-minimal/mem.spin +++ b/formal-model/ooomem-double-update-minimal/mem.spin @@ -40,26 +40,6 @@ #define CLEAR_TOKENS(state, bits) \ state = (state) & ~(bits) -/* - * Bit encoding, proc_one_produced : - */ - -#define P1_PROD_NONE (1 << 0) - -#define P1_READ_ONE (1 << 1) -#define P1_RMB (1 << 2) -#define P1_READ_TWO (1 << 3) - -int proc_one_produced; - -#define P2_PROD_NONE (1 << 0) - -#define P2_WRITE_ONE (1 << 1) -#define P2_WMB (1 << 2) -#define P2_WRITE_TWO (1 << 3) - -int proc_two_produced; - #define NR_PROCS 2 #define get_pid() (_pid) @@ -168,6 +148,18 @@ DECLARE_CACHED_VAR(byte, beta, 0); byte read_one = 2; byte read_two = 2; +/* + * Bit encoding, proc_one_produced : + */ + +#define P1_PROD_NONE (1 << 0) + +#define P1_READ_ONE (1 << 1) +#define P1_RMB (1 << 2) +#define P1_READ_TWO (1 << 3) + +int proc_one_produced; + active proctype test_proc_one() { assert(get_pid() < NR_PROCS); @@ -203,6 +195,19 @@ active proctype test_proc_one() assert(read_one != 1 || read_two == 1); } + +/* + * Bit encoding, proc_two_produced : + */ + +#define P2_PROD_NONE (1 << 0) + +#define P2_WRITE_ONE (1 << 1) +#define P2_WMB (1 << 2) +#define P2_WRITE_TWO (1 << 3) + +int proc_two_produced; + active proctype test_proc_two() { assert(get_pid() < NR_PROCS); diff --git a/formal-model/ooomem-two-writes/mem.spin b/formal-model/ooomem-two-writes/mem.spin index 828ff4a..cb206d2 100644 --- a/formal-model/ooomem-two-writes/mem.spin +++ b/formal-model/ooomem-two-writes/mem.spin @@ -40,30 +40,6 @@ #define CLEAR_TOKENS(state, bits) \ state = (state) & ~(bits) -/* - * Bit encoding, proc_one_produced : - */ - -#define P1_PROD_NONE (1 << 0) - -#define P1_WRITE (1 << 1) -#define P1_WMB (1 << 2) -#define P1_SYNC_CORE (1 << 3) -#define P1_RMB (1 << 4) -#define P1_READ (1 << 5) - -int proc_one_produced; - -#define P2_PROD_NONE (1 << 0) - -#define P2_WRITE (1 << 1) -#define P2_WMB (1 << 2) -#define P2_SYNC_CORE (1 << 3) -#define P2_RMB (1 << 4) -#define P2_READ (1 << 5) - -int proc_two_produced; - #define NR_PROCS 2 #define get_pid() (_pid) @@ -172,6 +148,20 @@ DECLARE_CACHED_VAR(byte, beta, 0); byte read_one = 2; byte read_two = 2; +/* + * Bit encoding, proc_one_produced : + */ + +#define P1_PROD_NONE (1 << 0) + +#define P1_WRITE (1 << 1) +#define P1_WMB (1 << 2) +#define P1_SYNC_CORE (1 << 3) +#define P1_RMB (1 << 4) +#define P1_READ (1 << 5) + +int proc_one_produced; + active proctype test_proc_one() { assert(get_pid() < NR_PROCS); @@ -222,6 +212,21 @@ active proctype test_proc_one() assert(!(read_one == 0 && read_two == 0)); } + +/* + * Bit encoding, proc_two_produced : + */ + +#define P2_PROD_NONE (1 << 0) + +#define P2_WRITE (1 << 1) +#define P2_WMB (1 << 2) +#define P2_SYNC_CORE (1 << 3) +#define P2_RMB (1 << 4) +#define P2_READ (1 << 5) + +int proc_two_produced; + active proctype test_proc_two() { assert(get_pid() < NR_PROCS); -- 2.34.1 From 54843abcc17c8e8b7600ed635e966c6970d8d20f Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Sat, 9 May 2009 01:11:49 -0400 Subject: [PATCH 04/16] LGPL relicensing of IBM's contributions Add comments noting IBM's permission to relicense its contributions to the urcu.h and urcu.c files under the LGPLv2 license, or any later version. Signed-off-by: Paul E. McKenney Reviewed-by: Steven L. Bennett --- urcu.c | 2 ++ urcu.h | 2 ++ 2 files changed, 4 insertions(+) diff --git a/urcu.c b/urcu.c index 40514c3..337f764 100644 --- a/urcu.c +++ b/urcu.c @@ -6,6 +6,8 @@ * Copyright February 2009 - Mathieu Desnoyers * * Distributed under GPLv2 + * + * IBM's contributions to this file may be relicensed under LGPLv2 or later. */ #include diff --git a/urcu.h b/urcu.h index 0ff0877..819555e 100644 --- a/urcu.h +++ b/urcu.h @@ -15,6 +15,8 @@ * and rcu_dereference primitives come from the Linux kernel. * * Distributed under GPLv2 + * + * IBM's contributions to this file may be relicensed under LGPLv2 or later. */ #include -- 2.34.1 From ad7de003b45b3a7339b90208c321517c2dcbdc3e Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sat, 9 May 2009 10:48:38 -0400 Subject: [PATCH 05/16] Add ACCESS_ONCE to _STORE_SHARED We assume that the compiler does not reorder _STORE_SHARED across each other and wrt _READ_SHARED. We therefore need to mark this access as volatile. The compiler cannot reorder volatile accesses. Signed-off-by: Mathieu Desnoyers --- urcu.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/urcu.h b/urcu.h index 819555e..b43b280 100644 --- a/urcu.h +++ b/urcu.h @@ -87,7 +87,7 @@ */ #define _STORE_SHARED(x, v) \ do { \ - (x) = (v); \ + ACCESS_ONCE(x) = (v); \ } while (0) /* -- 2.34.1 From 121a5d44c8cc7197116df73854cb94c6cfbad0b0 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 10 May 2009 20:54:43 -0400 Subject: [PATCH 06/16] LGPLv2.1 relicensing Except the content of arch_x86.h and arch_ppc.h, everything that was not LGPL-compatible has been either rewritten or was simply a trivial one-liner. The only content which could still be non-LGPL licensable in this commit is : arch_ppc.h: atomic_inc() __xchg_u32() get_cycles (maybe ?) arch_x86.h: __xchg() Signed-off-by: Mathieu Desnoyers --- Makefile | 24 +++- arch_ppc.h | 29 +++++ arch_x86.h | 29 +++++ rcutorture.h | 8 +- test_rwlock_timing.c | 1 + test_urcu.c | 11 +- test_urcu_timing.c | 8 +- urcu.c | 58 +++++++-- urcu.h | 297 +++++-------------------------------------- urcutorture.c | 1 + 10 files changed, 179 insertions(+), 287 deletions(-) diff --git a/Makefile b/Makefile index 386856f..5842b26 100644 --- a/Makefile +++ b/Makefile @@ -1,15 +1,19 @@ -CFLAGS=-Wall -O2 -g +CFLAGS=-Wall -O2 -g -I. LDFLAGS=-lpthread #debug #CFLAGS=-Wall -g #CFLAGS+=-DDEBUG_FULL_MB +#Changing the signal number used by the library. SIGUSR1 by default. +#CFLAGS+=-DSIGURCU=SIGUSR2 + SRC_DEP=`echo $^ | sed 's/[^ ]*.h//g'` -all: test_urcu test_urcu_timing test_rwlock_timing test_urcu_yield urcu-asm.S \ - urcu-asm.o urcutorture urcutorture-yield +all: test_urcu test_urcu_dynamic_link test_urcu_timing \ + test_rwlock_timing test_urcu_yield urcu-asm.S \ + urcu-asm.o urcutorture urcutorture-yield liburcu.so pthreads-x86: clean cp api_x86.h api.h @@ -22,6 +26,9 @@ pthreads-ppc: clean test_urcu: urcu.o test_urcu.c urcu.h $(CC) ${CFLAGS} $(LDFLAGS) -o $@ $(SRC_DEP) +test_urcu_dynamic_link: urcu.o test_urcu.c urcu.h + $(CC) ${CFLAGS} -DDYNAMIC_LINK_TEST $(LDFLAGS) -o $@ $(SRC_DEP) + test_urcu_yield: urcu-yield.o test_urcu.c urcu.h $(CC) -DDEBUG_YIELD ${CFLAGS} $(LDFLAGS) -o $@ $(SRC_DEP) @@ -32,7 +39,10 @@ test_rwlock_timing: urcu.o test_rwlock_timing.c urcu.h $(CC) ${CFLAGS} $(LDFLAGS) -o $@ $(SRC_DEP) urcu.o: urcu.c urcu.h - $(CC) ${CFLAGS} $(LDFLAGS) -c -o $@ $(SRC_DEP) + $(CC) -fPIC ${CFLAGS} $(LDFLAGS) -c -o $@ $(SRC_DEP) + +liburcu.so: urcu.o + $(CC) -fPIC -shared -o $@ $< urcu-yield.o: urcu.c urcu.h $(CC) -DDEBUG_YIELD ${CFLAGS} $(LDFLAGS) -c -o $@ $(SRC_DEP) @@ -49,7 +59,11 @@ urcutorture: urcutorture.c urcu.o urcu.h rcutorture.h urcutorture-yield: urcutorture.c urcu-yield.o urcu.h rcutorture.h $(CC) -DDEBUG_YIELD ${CFLAGS} $(LDFLAGS) -o $@ $(SRC_DEP) -.PHONY: clean +.PHONY: clean install + +install: liburcu.so + cp -f liburcu.so /usr/lib/ + cp -f arch.h compiler.h urcu.h urcu-static.h /usr/include/ clean: rm -f *.o test_urcu test_urcu_timing test_rwlock_timing urcu-asm.S \ diff --git a/arch_ppc.h b/arch_ppc.h index 6dc5f3e..b43d08b 100644 --- a/arch_ppc.h +++ b/arch_ppc.h @@ -1,3 +1,6 @@ +#ifndef _ARCH_PPC_H +#define _ARCH_PPC_H + /* * arch_x86.h: Definitions for the x86 architecture, derived from Linux. * @@ -18,6 +21,8 @@ * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. */ +#include + #define CONFIG_HAVE_FENCE 1 #define CONFIG_HAVE_MEM_COHERENCY @@ -40,6 +45,28 @@ #define rmc() barrier() #define wmc() barrier() +/* Assume SMP machine, given we don't have this information */ +#define CONFIG_SMP 1 + +#ifdef CONFIG_SMP +#define smp_mb() mb() +#define smp_rmb() rmb() +#define smp_wmb() wmb() +#define smp_mc() mc() +#define smp_rmc() rmc() +#define smp_wmc() wmc() +#else +#define smp_mb() barrier() +#define smp_rmb() barrier() +#define smp_wmb() barrier() +#define smp_mc() barrier() +#define smp_rmc() barrier() +#define smp_wmc() barrier() +#endif + +/* Nop everywhere except on alpha. */ +#define smp_read_barrier_depends() + static inline void cpu_relax(void) { barrier(); @@ -150,3 +177,5 @@ static inline cycles_t get_cycles (void) return (((long long)h) << 32) + l; } } + +#endif /* _ARCH_PPC_H */ diff --git a/arch_x86.h b/arch_x86.h index 99ccd29..e924913 100644 --- a/arch_x86.h +++ b/arch_x86.h @@ -1,3 +1,6 @@ +#ifndef _ARCH_X86_H +#define _ARCH_X86_H + /* * arch_x86.h: Definitions for the x86 architecture, derived from Linux. * @@ -18,6 +21,8 @@ * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. */ +#include + /* Assume P4 or newer */ #define CONFIG_HAVE_FENCE 1 #define CONFIG_HAVE_MEM_COHERENCY @@ -51,6 +56,28 @@ #define rmc() barrier() #define wmc() barrier() +/* Assume SMP machine, given we don't have this information */ +#define CONFIG_SMP 1 + +#ifdef CONFIG_SMP +#define smp_mb() mb() +#define smp_rmb() rmb() +#define smp_wmb() wmb() +#define smp_mc() mc() +#define smp_rmc() rmc() +#define smp_wmc() wmc() +#else +#define smp_mb() barrier() +#define smp_rmb() barrier() +#define smp_wmb() barrier() +#define smp_mc() barrier() +#define smp_rmc() barrier() +#define smp_wmc() barrier() +#endif + +/* Nop everywhere except on alpha. */ +#define smp_read_barrier_depends() + /* REP NOP (PAUSE) is a good thing to insert into busy-wait loops. */ static inline void rep_nop(void) { @@ -135,3 +162,5 @@ static inline cycles_t get_cycles (void) rdtscll(ret); return ret; } + +#endif /* _ARCH_X86_H */ diff --git a/rcutorture.h b/rcutorture.h index 8681ef7..e123559 100644 --- a/rcutorture.h +++ b/rcutorture.h @@ -114,7 +114,7 @@ void *rcu_read_perf_test(void *arg) int me = (long)arg; long long n_reads_local = 0; - urcu_register_thread(); + rcu_register_thread(); run_on(me); atomic_inc(&nthreadsrunning); while (goflag == GOFLAG_INIT) @@ -132,7 +132,7 @@ void *rcu_read_perf_test(void *arg) } __get_thread_var(n_reads_pt) += n_reads_local; put_thread_offline(); - urcu_unregister_thread(); + rcu_unregister_thread(); return (NULL); } @@ -258,7 +258,7 @@ void *rcu_read_stress_test(void *arg) struct rcu_stress *p; int pc; - urcu_register_thread(); + rcu_register_thread(); while (goflag == GOFLAG_INIT) poll(NULL, 0, 1); mark_rcu_quiescent_state(); @@ -285,7 +285,7 @@ void *rcu_read_stress_test(void *arg) } } put_thread_offline(); - urcu_unregister_thread(); + rcu_unregister_thread(); return (NULL); } diff --git a/test_rwlock_timing.c b/test_rwlock_timing.c index 9ea2494..2c3d894 100644 --- a/test_rwlock_timing.c +++ b/test_rwlock_timing.c @@ -19,6 +19,7 @@ #include #include #include +#include #if defined(_syscall0) _syscall0(pid_t, gettid) diff --git a/test_urcu.c b/test_urcu.c index 129b33a..a044d53 100644 --- a/test_urcu.c +++ b/test_urcu.c @@ -34,6 +34,11 @@ static inline pid_t gettid(void) } #endif +#ifndef DYNAMIC_LINK_TEST +#define _LGPL_SOURCE +#else +#define debug_yield_read() +#endif #include "urcu.h" struct test_array { @@ -146,7 +151,7 @@ void *thr_reader(void *_count) printf("thread_begin %s, thread id : %lx, tid %lu\n", "reader", pthread_self(), (unsigned long)gettid()); - urcu_register_thread(); + rcu_register_thread(); for (;;) { rcu_read_lock(); @@ -160,7 +165,7 @@ void *thr_reader(void *_count) break; } - urcu_unregister_thread(); + rcu_unregister_thread(); *count = nr_reads; printf("thread_end %s, thread id : %lx, tid %lu\n", @@ -184,7 +189,7 @@ void *thr_writer(void *_count) if (old) assert(old->a == 8); new->a = 8; - old = urcu_publish_content(&test_rcu_pointer, new); + old = rcu_publish_content(&test_rcu_pointer, new); rcu_copy_mutex_unlock(); /* can be done after unlock */ if (old) diff --git a/test_urcu_timing.c b/test_urcu_timing.c index ac23846..a11532a 100644 --- a/test_urcu_timing.c +++ b/test_urcu_timing.c @@ -18,6 +18,7 @@ #include #include #include +#include #if defined(_syscall0) _syscall0(pid_t, gettid) @@ -34,6 +35,7 @@ static inline pid_t gettid(void) } #endif +#define _LGPL_SOURCE #include "urcu.h" pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER; @@ -86,7 +88,7 @@ void *thr_reader(void *arg) "reader", pthread_self(), (unsigned long)gettid()); sleep(2); - urcu_register_thread(); + rcu_register_thread(); time1 = get_cycles(); for (i = 0; i < OUTER_READ_LOOP; i++) { @@ -101,7 +103,7 @@ void *thr_reader(void *arg) } time2 = get_cycles(); - urcu_unregister_thread(); + rcu_unregister_thread(); reader_time[(unsigned long)arg] = time2 - time1; @@ -129,7 +131,7 @@ void *thr_writer(void *arg) assert(old->a == 8); } new->a = 8; - old = urcu_publish_content(&test_rcu_pointer, new); + old = rcu_publish_content(&test_rcu_pointer, new); rcu_copy_mutex_unlock(); /* can be done after unlock */ if (old) { diff --git a/urcu.c b/urcu.c index 337f764..7ab87c4 100644 --- a/urcu.c +++ b/urcu.c @@ -5,7 +5,7 @@ * * Copyright February 2009 - Mathieu Desnoyers * - * Distributed under GPLv2 + * Distributed under LGPLv2.1 * * IBM's contributions to this file may be relicensed under LGPLv2 or later. */ @@ -19,6 +19,8 @@ #include #include +#include "urcu-static.h" +/* Do not #define _LGPL_SOURCE to ensure we can emit the wrapper symbols */ #include "urcu.h" pthread_mutex_t urcu_mutex = PTHREAD_MUTEX_INITIALIZER; @@ -269,7 +271,47 @@ void synchronize_rcu(void) internal_urcu_unlock(); } -void urcu_add_reader(pthread_t id) +/* + * library wrappers to be used by non-LGPL compatible source code. + */ + +void rcu_read_lock(void) +{ + _rcu_read_lock(); +} + +void rcu_read_unlock(void) +{ + _rcu_read_unlock(); +} + +void *rcu_dereference(void *p) +{ + return _rcu_dereference(p); +} + +void *rcu_assign_pointer_sym(void **p, void *v) +{ + wmb(); + return STORE_SHARED(p, v); +} + +void *rcu_xchg_pointer_sym(void **p, void *v) +{ + wmb(); + return xchg(p, v); +} + +void *rcu_publish_content_sym(void **p, void *v) +{ + void *oldptr; + + oldptr = _rcu_xchg_pointer(p, v); + synchronize_rcu(); + return oldptr; +} + +static void rcu_add_reader(pthread_t id) { struct reader_registry *oldarray; @@ -299,7 +341,7 @@ void urcu_add_reader(pthread_t id) * Never shrink (implementation limitation). * This is O(nb threads). Eventually use a hash table. */ -void urcu_remove_reader(pthread_t id) +static void rcu_remove_reader(pthread_t id) { struct reader_registry *index; @@ -318,22 +360,22 @@ void urcu_remove_reader(pthread_t id) assert(0); } -void urcu_register_thread(void) +void rcu_register_thread(void) { internal_urcu_lock(); - urcu_add_reader(pthread_self()); + rcu_add_reader(pthread_self()); internal_urcu_unlock(); } -void urcu_unregister_thread(void) +void rcu_unregister_thread(void) { internal_urcu_lock(); - urcu_remove_reader(pthread_self()); + rcu_remove_reader(pthread_self()); internal_urcu_unlock(); } #ifndef DEBUG_FULL_MB -void sigurcu_handler(int signo, siginfo_t *siginfo, void *context) +static void sigurcu_handler(int signo, siginfo_t *siginfo, void *context) { /* * Executing this smp_mb() is the only purpose of this signal handler. diff --git a/urcu.h b/urcu.h index b43b280..0b0d232 100644 --- a/urcu.h +++ b/urcu.h @@ -8,13 +8,15 @@ * * Copyright February 2009 - Mathieu Desnoyers * - * Credits for Paul e. McKenney + * Credits for Paul E. McKenney * for inspiration coming from the Linux kernel RCU and rcu-preempt. * - * The barrier, mb, rmb, wmb, atomic_inc, smp_read_barrier_depends, ACCESS_ONCE - * and rcu_dereference primitives come from the Linux kernel. + * LGPL-compatible code should include this header with : * - * Distributed under GPLv2 + * #define _LGPL_SOURCE + * #include + * + * Distributed under LGPLv2.1 * * IBM's contributions to this file may be relicensed under LGPLv2 or later. */ @@ -22,288 +24,55 @@ #include #include -/* The "volatile" is due to gcc bugs */ -#define barrier() __asm__ __volatile__("": : :"memory") - -#define likely(x) __builtin_expect(!!(x), 1) -#define unlikely(x) __builtin_expect(!!(x), 0) - -/* Assume SMP machine, given we don't have this information */ -#define CONFIG_SMP 1 - - -#ifdef CONFIG_SMP -#define smp_mb() mb() -#define smp_rmb() rmb() -#define smp_wmb() wmb() -#define smp_mc() mc() -#define smp_rmc() rmc() -#define smp_wmc() wmc() -#else -#define smp_mb() barrier() -#define smp_rmb() barrier() -#define smp_wmb() barrier() -#define smp_mc() barrier() -#define smp_rmc() barrier() -#define smp_wmc() barrier() -#endif - -#include "arch.h" - -/* Nop everywhere except on alpha. */ -#define smp_read_barrier_depends() - -/* - * Prevent the compiler from merging or refetching accesses. The compiler - * is also forbidden from reordering successive instances of ACCESS_ONCE(), - * but only when the compiler is aware of some particular ordering. One way - * to make the compiler aware of ordering is to put the two invocations of - * ACCESS_ONCE() in different C statements. - * - * This macro does absolutely -nothing- to prevent the CPU from reordering, - * merging, or refetching absolutely anything at any time. Its main intended - * use is to mediate communication between process-level code and irq/NMI - * handlers, all running on the same CPU. - */ -#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x)) - -/* - * Identify a shared load. A smp_rmc() or smp_mc() should come before the load. - */ -#define _LOAD_SHARED(p) ACCESS_ONCE(p) - -/* - * Load a data from shared memory, doing a cache flush if required. - */ -#define LOAD_SHARED(p) \ - ({ \ - smp_rmc(); \ - _LOAD_SHARED(p); \ - }) - +#ifdef _LGPL_SOURCE -/* - * Identify a shared store. A smp_wmc() or smp_mc() should follow the store. - */ -#define _STORE_SHARED(x, v) \ - do { \ - ACCESS_ONCE(x) = (v); \ - } while (0) +#include /* - * Store v into x, where x is located in shared memory. Performs the required - * cache flush after writing. + * Mappings for static use of the userspace RCU library. + * Should only be used in LGPL-compatible code. */ -#define STORE_SHARED(x, v) \ - do { \ - _STORE_SHARED(x, v); \ - smp_wmc(); \ - } while (0) -/** - * rcu_dereference - fetch an RCU-protected pointer in an - * RCU read-side critical section. This pointer may later - * be safely dereferenced. - * - * Inserts memory barriers on architectures that require them - * (currently only the Alpha), and, more importantly, documents - * exactly which pointers are protected by RCU. - */ +#define rcu_dereference _rcu_dereference +#define rcu_read_lock _rcu_read_lock +#define rcu_read_unlock _rcu_read_unlock -#define rcu_dereference(p) ({ \ - typeof(p) _________p1 = LOAD_SHARED(p); \ - smp_read_barrier_depends(); \ - (_________p1); \ - }) +#define rcu_assign_pointer _rcu_assign_pointer +#define rcu_xchg_pointer _rcu_xchg_pointer +#define rcu_publish_content _rcu_publish_content -#define SIGURCU SIGUSR1 +#else /* !_LGPL_SOURCE */ /* - * If a reader is really non-cooperative and refuses to commit its - * urcu_active_readers count to memory (there is no barrier in the reader - * per-se), kick it after a few loops waiting for it. + * library wrappers to be used by non-LGPL compatible source code. */ -#define KICK_READER_LOOPS 10000 - -#ifdef DEBUG_YIELD -#include -#include -#include -#include -#define YIELD_READ (1 << 0) -#define YIELD_WRITE (1 << 1) +extern void rcu_read_lock(void); +extern void rcu_read_unlock(void); -/* Updates without DEBUG_FULL_MB are much slower. Account this in the delay */ -#ifdef DEBUG_FULL_MB -/* maximum sleep delay, in us */ -#define MAX_SLEEP 50 -#else -#define MAX_SLEEP 30000 -#endif +extern void *rcu_dereference(void *p); -extern unsigned int yield_active; -extern unsigned int __thread rand_yield; +extern void *rcu_assign_pointer_sym(void **p, void *v); -static inline void debug_yield_read(void) -{ - if (yield_active & YIELD_READ) - if (rand_r(&rand_yield) & 0x1) - usleep(rand_r(&rand_yield) % MAX_SLEEP); -} +#define rcu_assign_pointer(p, v) \ + rcu_assign_pointer_sym((void **)(p), (v)) -static inline void debug_yield_write(void) -{ - if (yield_active & YIELD_WRITE) - if (rand_r(&rand_yield) & 0x1) - usleep(rand_r(&rand_yield) % MAX_SLEEP); -} +extern void *rcu_xchg_pointer_sym(void **p, void *v); +#define rcu_xchg_pointer(p, v) \ + rcu_xchg_pointer_sym((void **)(p), (v)) -static inline void debug_yield_init(void) -{ - rand_yield = time(NULL) ^ pthread_self(); -} -#else -static inline void debug_yield_read(void) -{ -} +extern void *rcu_publish_content_sym(void **p, void *v); +#define rcu_publish_content(p, v) \ + rcu_publish_content_sym((void **)(p), (v)) -static inline void debug_yield_write(void) -{ -} - -static inline void debug_yield_init(void) -{ - -} -#endif - -#ifdef DEBUG_FULL_MB -static inline void reader_barrier() -{ - smp_mb(); -} -#else -static inline void reader_barrier() -{ - barrier(); -} -#endif - -/* - * The trick here is that RCU_GP_CTR_BIT must be a multiple of 8 so we can use a - * full 8-bits, 16-bits or 32-bits bitmask for the lower order bits. - */ -#define RCU_GP_COUNT (1UL << 0) -/* Use the amount of bits equal to half of the architecture long size */ -#define RCU_GP_CTR_BIT (1UL << (sizeof(long) << 2)) -#define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BIT - 1) - -/* - * Global quiescent period counter with low-order bits unused. - * Using a int rather than a char to eliminate false register dependencies - * causing stalls on some architectures. - */ -extern long urcu_gp_ctr; - -extern long __thread urcu_active_readers; - -static inline int rcu_old_gp_ongoing(long *value) -{ - long v; - - if (value == NULL) - return 0; - /* - * Make sure both tests below are done on the same version of *value - * to insure consistency. - */ - v = LOAD_SHARED(*value); - return (v & RCU_GP_CTR_NEST_MASK) && - ((v ^ urcu_gp_ctr) & RCU_GP_CTR_BIT); -} - -static inline void rcu_read_lock(void) -{ - long tmp; - - tmp = urcu_active_readers; - /* urcu_gp_ctr = RCU_GP_COUNT | (~RCU_GP_CTR_BIT or RCU_GP_CTR_BIT) */ - /* - * The data dependency "read urcu_gp_ctr, write urcu_active_readers", - * serializes those two memory operations. The memory barrier in the - * signal handler ensures we receive the proper memory commit barriers - * required by _STORE_SHARED and _LOAD_SHARED whenever communication - * with the writer is needed. - */ - if (likely(!(tmp & RCU_GP_CTR_NEST_MASK))) - _STORE_SHARED(urcu_active_readers, _LOAD_SHARED(urcu_gp_ctr)); - else - _STORE_SHARED(urcu_active_readers, tmp + RCU_GP_COUNT); - /* - * Increment active readers count before accessing the pointer. - * See force_mb_all_threads(). - */ - reader_barrier(); -} - -static inline void rcu_read_unlock(void) -{ - reader_barrier(); - /* - * Finish using rcu before decrementing the pointer. - * See force_mb_all_threads(). - */ - _STORE_SHARED(urcu_active_readers, urcu_active_readers - RCU_GP_COUNT); -} - -/** - * rcu_assign_pointer - assign (publicize) a pointer to a newly - * initialized structure that will be dereferenced by RCU read-side - * critical sections. Returns the value assigned. - * - * Inserts memory barriers on architectures that require them - * (pretty much all of them other than x86), and also prevents - * the compiler from reordering the code that initializes the - * structure after the pointer assignment. More importantly, this - * call documents which pointers will be dereferenced by RCU read-side - * code. - */ - -#define rcu_assign_pointer(p, v) \ - ({ \ - if (!__builtin_constant_p(v) || \ - ((v) != NULL)) \ - wmb(); \ - STORE_SHARED(p, v); \ - }) - -#define rcu_xchg_pointer(p, v) \ - ({ \ - if (!__builtin_constant_p(v) || \ - ((v) != NULL)) \ - wmb(); \ - xchg(p, v); \ - }) +#endif /* !_LGPL_SOURCE */ extern void synchronize_rcu(void); -/* - * Exchanges the pointer and waits for quiescent state. - * The pointer returned can be freed. - */ -#define urcu_publish_content(p, v) \ - ({ \ - void *oldptr; \ - oldptr = rcu_xchg_pointer(p, v); \ - synchronize_rcu(); \ - oldptr; \ - }) - /* * Reader thread registration. */ -extern void urcu_register_thread(void); -extern void urcu_unregister_thread(void); +extern void rcu_register_thread(void); +extern void rcu_unregister_thread(void); #endif /* _URCU_H */ diff --git a/urcutorture.c b/urcutorture.c index 258413a..75256f9 100644 --- a/urcutorture.c +++ b/urcutorture.c @@ -4,5 +4,6 @@ #include #include #include "api.h" +#define _LGPL_SOURCE #include "urcu.h" #include "rcutorture.h" -- 2.34.1 From af02d47e5d0712e5ccde6d8f1ee89f18de798cad Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 10 May 2009 22:15:08 -0400 Subject: [PATCH 07/16] LGPL relicensing part 2 Rewrote the non-trivial functions in arch_ppc.h and arch_x86.h. Added complete header license declarations. Created LICENSE file to explain the library licence. Signed-off-by: Mathieu Desnoyers --- LICENSE | 32 +++ Makefile | 3 +- arch_ppc.h | 151 ++++++------- arch_x86.h | 85 ++++---- compiler.h | 48 +++++ gpl-2.0.txt | 339 +++++++++++++++++++++++++++++ lgpl-2.1.txt | 504 +++++++++++++++++++++++++++++++++++++++++++ test_rwlock_timing.c | 14 +- test_urcu.c | 14 +- test_urcu_timing.c | 14 +- urcu.c | 17 +- urcu.h | 20 +- 12 files changed, 1115 insertions(+), 126 deletions(-) create mode 100644 LICENSE create mode 100644 compiler.h create mode 100644 gpl-2.0.txt create mode 100644 lgpl-2.1.txt diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..f2b5228 --- /dev/null +++ b/LICENSE @@ -0,0 +1,32 @@ +Userspace RCU library licensing +Mathieu Desnoyers +May 10, 2009 + +The library part is distributed under LGPLv2.1 or later. See lgpl-2.1.txt for +details. This applies to : + +urcu.h +urcu.c +urcu-static.h +arch_x86.h +arch_ppc.h + +LGPL-compatible source code can statically use the library header using : + +#define _LGPL_SOURCE +#include + +Dynamic-only linking with the LGPL library is used if _LGPL_SOURCE is not +defined. It permits relinking with newer versions of the library, which is +required by the LGPL license. + +Library test code is distributed under the GPLv2 license. See gpl-2.0.txt for +details. This applies to : + +urcutorture.h +urcutorture.c +api_x86.h +api_ppc.h +test_urcu.c +test_urcu_yield.c +test_rwlock_timing.c diff --git a/Makefile b/Makefile index 5842b26..093bf66 100644 --- a/Makefile +++ b/Makefile @@ -67,4 +67,5 @@ install: liburcu.so clean: rm -f *.o test_urcu test_urcu_timing test_rwlock_timing urcu-asm.S \ - test_urcu_yield urcutorture urcutorture-yield + test_urcu_yield urcutorture urcutorture-yield liburcu.so \ + test_urcu_dynamic_link diff --git a/arch_ppc.h b/arch_ppc.h index b43d08b..1a34024 100644 --- a/arch_ppc.h +++ b/arch_ppc.h @@ -2,23 +2,24 @@ #define _ARCH_PPC_H /* - * arch_x86.h: Definitions for the x86 architecture, derived from Linux. + * arch_ppc.h: trivial definitions for the powerpc architecture. * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; but only version 2 of the License given - * that this comes from the Linux kernel. + * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. + * Copyright (c) 2009 Mathieu Desnoyers * - * This program is distributed in the hope that it will be useful, + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. +* + * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. * - * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include @@ -26,6 +27,10 @@ #define CONFIG_HAVE_FENCE 1 #define CONFIG_HAVE_MEM_COHERENCY +#ifndef BITS_PER_LONG +#define BITS_PER_LONG (sizeof(unsigned long) * 8) +#endif + #define mb() asm volatile("sync":::"memory") #define rmb() asm volatile("sync":::"memory") #define wmb() asm volatile("sync"::: "memory") @@ -76,25 +81,6 @@ static inline void cpu_relax(void) #define LWSYNC_ON_SMP "\n\tlwsync\n" #define ISYNC_ON_SMP "\n\tisync\n" -#ifndef _INCLUDE_API_H - -static __inline__ void atomic_inc(int *v) -{ - int t; - - __asm__ __volatile__( -"1: lwarx %0,0,%2 # atomic_inc\n\ - addic %0,%0,1\n" - PPC405_ERR77(0,%2) -" stwcx. %0,0,%2 \n\ - bne- 1b" - : "=&r" (t), "+m" (v) - : "r" (&v) - : "cc", "xer"); -} - -#endif /* #ifndef _INCLUDE_API_H */ - struct __xchg_dummy { unsigned long a[100]; }; @@ -103,78 +89,99 @@ struct __xchg_dummy { #ifndef _INCLUDE_API_H /* - * Atomic exchange - * - * Changes the memory location '*ptr' to be val and returns - * the previous value stored there. + * Exchange the 32-bits value pointed to by p, returns the old value. + * Might not work with PPC405 (see err 77). */ -static __always_inline unsigned long -__xchg_u32(volatile void *p, unsigned long val) +static __always_inline +unsigned int __xchg_u32(volatile void *p, unsigned int val) { - unsigned long prev; - - __asm__ __volatile__( - LWSYNC_ON_SMP -"1: lwarx %0,0,%2 \n" - PPC405_ERR77(0,%2) -" stwcx. %3,0,%2 \n\ - bne- 1b" - ISYNC_ON_SMP - : "=&r" (prev), "+m" (*(volatile unsigned int *)p) - : "r" (p), "r" (val) - : "cc", "memory"); - + unsigned int prev; + + __asm__ __volatile__(LWSYNC_ON_SMP + "1:\t" "lwarx %0,0,%2\n" + "stwcx. %3,0,%2\n" + "bne- 1b" + ISYNC_ON_SMP + : "=&r" (prev), "+m" (*(volatile unsigned int *)p) + : "r" (p), "r" (val) + : "cc", "memory"); return prev; } +#if (BITS_PER_LONG == 64) /* - * This function doesn't exist, so you'll get a linker error - * if something tries to do an invalid xchg(). + * Exchange the 64-bits value pointed to by p, returns the old value. + * Might not work with PPC405 (see err 77). */ -extern void __xchg_called_with_bad_pointer(void); +static __always_inline +unsigned long __xchg_u64(volatile void *p, unsigned long val) +{ + unsigned long prev; + + __asm__ __volatile__(LWSYNC_ON_SMP + "1:\t" "ldarx %0,0,%2\n" + "stdcx. %3,0,%2\n" + "bne- 1b" + ISYNC_ON_SMP + : "=&r" (prev), "+m" (*(volatile unsigned long *)p) + : "r" (p), "r" (val) + : "cc", "memory"); + return prev; +} +#endif -static __always_inline unsigned long -__xchg(volatile void *ptr, unsigned long x, unsigned int size) +static __always_inline +unsigned long __xchg(volatile void *ptr, unsigned long x, int size) { switch (size) { case 4: return __xchg_u32(ptr, x); -#ifdef CONFIG_PPC64 +#if (BITS_PER_LONG == 64) case 8: return __xchg_u64(ptr, x); #endif } - __xchg_called_with_bad_pointer(); return x; } -#define xchg(ptr,x) \ - ({ \ - __typeof__(*(ptr)) _x_ = (x); \ - (__typeof__(*(ptr))) __xchg((ptr), (unsigned long)_x_, sizeof(*(ptr))); \ - }) +/* + * note : xchg should only be used with pointers to 32 or 64-bits elements. + * No build-time check is done on the element size because depending on + * non-referenced unexisting symbol at link time to provide an error message + * only work when compiling with optimizations. + */ +#define xchg(ptr, v) \ + ((__typeof__(*(ptr)))__xchg((ptr), (unsigned long)(v), sizeof(*(ptr)))) #endif /* #ifndef _INCLUDE_API_H */ -#define mftbl() ({unsigned long rval; \ - asm volatile("mftbl %0" : "=r" (rval)); rval;}) -#define mftbu() ({unsigned long rval; \ - asm volatile("mftbu %0" : "=r" (rval)); rval;}) +#define mftbl() \ + ({ \ + unsigned long rval; \ + asm volatile("mftbl %0" : "=r" (rval)); \ + rval; \ + }) + +#define mftbu() \ + ({ \ + unsigned long rval; \ + asm volatile("mftbu %0" : "=r" (rval)); \ + rval; \ + }) typedef unsigned long long cycles_t; static inline cycles_t get_cycles (void) { - long h; - long l; + long h, l; for (;;) { h = mftbu(); - smp_mb(); + barrier(); l = mftbl(); - smp_mb(); + barrier(); if (mftbu() == h) - return (((long long)h) << 32) + l; + return (((cycles_t) h) << 32) + l; } } diff --git a/arch_x86.h b/arch_x86.h index e924913..01b5d50 100644 --- a/arch_x86.h +++ b/arch_x86.h @@ -2,23 +2,24 @@ #define _ARCH_X86_H /* - * arch_x86.h: Definitions for the x86 architecture, derived from Linux. + * arch_x86.h: trivial definitions for the x86 architecture. * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; but only version 2 of the License given - * that this comes from the Linux kernel. + * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. + * Copyright (c) 2009 Mathieu Desnoyers * - * This program is distributed in the hope that it will be useful, + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. +* + * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. * - * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include @@ -27,6 +28,10 @@ #define CONFIG_HAVE_FENCE 1 #define CONFIG_HAVE_MEM_COHERENCY +#ifndef BITS_PER_LONG +#define BITS_PER_LONG (sizeof(unsigned long) * 8) +#endif + #ifdef CONFIG_HAVE_FENCE #define mb() asm volatile("mfence":::"memory") #define rmb() asm volatile("lfence":::"memory") @@ -89,75 +94,69 @@ static inline void cpu_relax(void) rep_nop(); } -#ifndef _INCLUDE_API_H +#define xchg(ptr, v) \ + ((__typeof__(*(ptr)))__xchg((ptr), (unsigned long)(v), sizeof(*(ptr)))) -static inline void atomic_inc(int *v) -{ - asm volatile("lock; incl %0" - : "+m" (*v)); -} - -#endif /* #ifndef _INCLUDE_API_H */ - -#define xchg(ptr, v) \ - ((__typeof__(*(ptr)))__xchg((unsigned long)(v), (ptr), sizeof(*(ptr)))) - -struct __xchg_dummy { +struct __xchg_ptr_as_array { unsigned long a[100]; }; -#define __xg(x) ((struct __xchg_dummy *)(x)) + +#define __xchg_ptr_as_array(x) ((struct __xchg_ptr_as_array *)(x)) /* - * Note: no "lock" prefix even on SMP: xchg always implies lock anyway - * Note 2: xchg has side effect, so that attribute volatile is necessary, - * but generally the primitive is invalid, *ptr is output argument. --ANK + * xchg always implies a "lock" prefix, even on UP. See Intel documentation. + * volatile attribute is neccessary due to xchg side effect. + * *ptr is an output argument. * x is considered local, ptr is considered remote. */ -static inline unsigned long __xchg(unsigned long x, volatile void *ptr, +static inline unsigned long __xchg(volatile void *ptr, unsigned long x, int size) { switch (size) { case 1: asm volatile("xchgb %b0,%1" : "=q" (x) - : "m" (*__xg(ptr)), "0" (x) + : "m" (*__xchg_ptr_as_array(ptr)), "0" (x) : "memory"); break; case 2: asm volatile("xchgw %w0,%1" : "=r" (x) - : "m" (*__xg(ptr)), "0" (x) + : "m" (*__xchg_ptr_as_array(ptr)), "0" (x) : "memory"); break; case 4: asm volatile("xchgl %k0,%1" : "=r" (x) - : "m" (*__xg(ptr)), "0" (x) + : "m" (*__xchg_ptr_as_array(ptr)), "0" (x) : "memory"); break; +#if (BITS_PER_LONG == 64) case 8: asm volatile("xchgq %0,%1" : "=r" (x) - : "m" (*__xg(ptr)), "0" (x) + : "m" (*__xchg_ptr_as_array(ptr)), "0" (x) : "memory"); break; +#endif } smp_wmc(); return x; } - -#define rdtscll(val) do { \ - unsigned int __a,__d; \ - asm volatile("rdtsc" : "=a" (__a), "=d" (__d)); \ - (val) = ((unsigned long long)__a) | (((unsigned long long)__d)<<32); \ -} while(0) +#define rdtscll(val) \ + do { \ + unsigned int __a, __d; \ + asm volatile("rdtsc" : "=a" (__a), "=d" (__d)); \ + (val) = ((unsigned long long)__a) \ + | (((unsigned long long)__d) << 32); \ + } while(0) typedef unsigned long long cycles_t; -static inline cycles_t get_cycles (void) +static inline cycles_t get_cycles(void) { - unsigned long long ret = 0; + cycles_t ret = 0; rdtscll(ret); return ret; diff --git a/compiler.h b/compiler.h new file mode 100644 index 0000000..2507ec8 --- /dev/null +++ b/compiler.h @@ -0,0 +1,48 @@ +#ifndef _COMPILER_H +#define _COMPILER_H + +/* + * compiler.h + * + * Compiler definitions. + * + * Copyright (c) 2009 Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. +* + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + * IBM's contributions to this file may be relicensed under LGPLv2 or later. + */ + +/* The "volatile" is due to gcc bugs */ +#define barrier() __asm__ __volatile__("": : :"memory") + +#define likely(x) __builtin_expect(!!(x), 1) +#define unlikely(x) __builtin_expect(!!(x), 0) + +/* + * Instruct the compiler to perform only a single access to a variable + * (prohibits merging and refetching). The compiler is also forbidden to reorder + * successive instances of ACCESS_ONCE(), but only when the compiler is aware of + * particular ordering. Compiler ordering can be ensured, for example, by + * putting two ACCESS_ONCE() in separate C statements. + * + * This macro does absolutely -nothing- to prevent the CPU from reordering, + * merging, or refetching absolutely anything at any time. Its main intended + * use is to mediate communication between process-level code and irq/NMI + * handlers, all running on the same CPU. + */ +#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x)) + +#endif /* _COMPILER_H */ diff --git a/gpl-2.0.txt b/gpl-2.0.txt new file mode 100644 index 0000000..d511905 --- /dev/null +++ b/gpl-2.0.txt @@ -0,0 +1,339 @@ + GNU GENERAL PUBLIC LICENSE + Version 2, June 1991 + + Copyright (C) 1989, 1991 Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +License is intended to guarantee your freedom to share and change free +software--to make sure the software is free for all its users. This +General Public License applies to most of the Free Software +Foundation's software and to any other program whose authors commit to +using it. (Some other Free Software Foundation software is covered by +the GNU Lesser General Public License instead.) You can apply it to +your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +this service if you wish), that you receive source code or can get it +if you want it, that you can change the software or use pieces of it +in new free programs; and that you know you can do these things. + + To protect your rights, we need to make restrictions that forbid +anyone to deny you these rights or to ask you to surrender the rights. +These restrictions translate to certain responsibilities for you if you +distribute copies of the software, or if you modify it. + + For example, if you distribute copies of such a program, whether +gratis or for a fee, you must give the recipients all the rights that +you have. You must make sure that they, too, receive or can get the +source code. And you must show them these terms so they know their +rights. + + We protect your rights with two steps: (1) copyright the software, and +(2) offer you this license which gives you legal permission to copy, +distribute and/or modify the software. + + Also, for each author's protection and ours, we want to make certain +that everyone understands that there is no warranty for this free +software. If the software is modified by someone else and passed on, we +want its recipients to know that what they have is not the original, so +that any problems introduced by others will not reflect on the original +authors' reputations. + + Finally, any free program is threatened constantly by software +patents. We wish to avoid the danger that redistributors of a free +program will individually obtain patent licenses, in effect making the +program proprietary. To prevent this, we have made it clear that any +patent must be licensed for everyone's free use or not licensed at all. + + The precise terms and conditions for copying, distribution and +modification follow. + + GNU GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License applies to any program or other work which contains +a notice placed by the copyright holder saying it may be distributed +under the terms of this General Public License. The "Program", below, +refers to any such program or work, and a "work based on the Program" +means either the Program or any derivative work under copyright law: +that is to say, a work containing the Program or a portion of it, +either verbatim or with modifications and/or translated into another +language. (Hereinafter, translation is included without limitation in +the term "modification".) Each licensee is addressed as "you". + +Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running the Program is not restricted, and the output from the Program +is covered only if its contents constitute a work based on the +Program (independent of having been made by running the Program). +Whether that is true depends on what the Program does. + + 1. You may copy and distribute verbatim copies of the Program's +source code as you receive it, in any medium, provided that you +conspicuously and appropriately publish on each copy an appropriate +copyright notice and disclaimer of warranty; keep intact all the +notices that refer to this License and to the absence of any warranty; +and give any other recipients of the Program a copy of this License +along with the Program. + +You may charge a fee for the physical act of transferring a copy, and +you may at your option offer warranty protection in exchange for a fee. + + 2. You may modify your copy or copies of the Program or any portion +of it, thus forming a work based on the Program, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) You must cause the modified files to carry prominent notices + stating that you changed the files and the date of any change. + + b) You must cause any work that you distribute or publish, that in + whole or in part contains or is derived from the Program or any + part thereof, to be licensed as a whole at no charge to all third + parties under the terms of this License. + + c) If the modified program normally reads commands interactively + when run, you must cause it, when started running for such + interactive use in the most ordinary way, to print or display an + announcement including an appropriate copyright notice and a + notice that there is no warranty (or else, saying that you provide + a warranty) and that users may redistribute the program under + these conditions, and telling the user how to view a copy of this + License. (Exception: if the Program itself is interactive but + does not normally print such an announcement, your work based on + the Program is not required to print an announcement.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Program, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Program, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Program. + +In addition, mere aggregation of another work not based on the Program +with the Program (or with a work based on the Program) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may copy and distribute the Program (or a work based on it, +under Section 2) in object code or executable form under the terms of +Sections 1 and 2 above provided that you also do one of the following: + + a) Accompany it with the complete corresponding machine-readable + source code, which must be distributed under the terms of Sections + 1 and 2 above on a medium customarily used for software interchange; or, + + b) Accompany it with a written offer, valid for at least three + years, to give any third party, for a charge no more than your + cost of physically performing source distribution, a complete + machine-readable copy of the corresponding source code, to be + distributed under the terms of Sections 1 and 2 above on a medium + customarily used for software interchange; or, + + c) Accompany it with the information you received as to the offer + to distribute corresponding source code. (This alternative is + allowed only for noncommercial distribution and only if you + received the program in object code or executable form with such + an offer, in accord with Subsection b above.) + +The source code for a work means the preferred form of the work for +making modifications to it. For an executable work, complete source +code means all the source code for all modules it contains, plus any +associated interface definition files, plus the scripts used to +control compilation and installation of the executable. However, as a +special exception, the source code distributed need not include +anything that is normally distributed (in either source or binary +form) with the major components (compiler, kernel, and so on) of the +operating system on which the executable runs, unless that component +itself accompanies the executable. + +If distribution of executable or object code is made by offering +access to copy from a designated place, then offering equivalent +access to copy the source code from the same place counts as +distribution of the source code, even though third parties are not +compelled to copy the source along with the object code. + + 4. You may not copy, modify, sublicense, or distribute the Program +except as expressly provided under this License. Any attempt +otherwise to copy, modify, sublicense or distribute the Program is +void, and will automatically terminate your rights under this License. +However, parties who have received copies, or rights, from you under +this License will not have their licenses terminated so long as such +parties remain in full compliance. + + 5. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Program or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Program (or any work based on the +Program), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Program or works based on it. + + 6. Each time you redistribute the Program (or any work based on the +Program), the recipient automatically receives a license from the +original licensor to copy, distribute or modify the Program subject to +these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties to +this License. + + 7. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Program at all. For example, if a patent +license would not permit royalty-free redistribution of the Program by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Program. + +If any portion of this section is held invalid or unenforceable under +any particular circumstance, the balance of the section is intended to +apply and the section as a whole is intended to apply in other +circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system, which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 8. If the distribution and/or use of the Program is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Program under this License +may add an explicit geographical distribution limitation excluding +those countries, so that distribution is permitted only in or among +countries not thus excluded. In such case, this License incorporates +the limitation as if written in the body of this License. + + 9. The Free Software Foundation may publish revised and/or new versions +of the General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + +Each version is given a distinguishing version number. If the Program +specifies a version number of this License which applies to it and "any +later version", you have the option of following the terms and conditions +either of that version or of any later version published by the Free +Software Foundation. If the Program does not specify a version number of +this License, you may choose any version ever published by the Free Software +Foundation. + + 10. If you wish to incorporate parts of the Program into other free +programs whose distribution conditions are different, write to the author +to ask for permission. For software which is copyrighted by the Free +Software Foundation, write to the Free Software Foundation; we sometimes +make exceptions for this. Our decision will be guided by the two goals +of preserving the free status of all derivatives of our free software and +of promoting the sharing and reuse of software generally. + + NO WARRANTY + + 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY +FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN +OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES +PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED +OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS +TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE +PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, +REPAIR OR CORRECTION. + + 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR +REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, +INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING +OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED +TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY +YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER +PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE +POSSIBILITY OF SUCH DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these terms. + + To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least +the "copyright" line and a pointer to where the full notice is found. + + + Copyright (C) + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + +Also add information on how to contact you by electronic and paper mail. + +If the program is interactive, make it output a short notice like this +when it starts in an interactive mode: + + Gnomovision version 69, Copyright (C) year name of author + Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. + This is free software, and you are welcome to redistribute it + under certain conditions; type `show c' for details. + +The hypothetical commands `show w' and `show c' should show the appropriate +parts of the General Public License. Of course, the commands you use may +be called something other than `show w' and `show c'; they could even be +mouse-clicks or menu items--whatever suits your program. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the program, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the program + `Gnomovision' (which makes passes at compilers) written by James Hacker. + + , 1 April 1989 + Ty Coon, President of Vice + +This General Public License does not permit incorporating your program into +proprietary programs. If your program is a subroutine library, you may +consider it more useful to permit linking proprietary applications with the +library. If this is what you want to do, use the GNU Lesser General +Public License instead of this License. diff --git a/lgpl-2.1.txt b/lgpl-2.1.txt new file mode 100644 index 0000000..602bfc9 --- /dev/null +++ b/lgpl-2.1.txt @@ -0,0 +1,504 @@ + GNU LESSER GENERAL PUBLIC LICENSE + Version 2.1, February 1999 + + Copyright (C) 1991, 1999 Free Software Foundation, Inc. + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + +[This is the first released version of the Lesser GPL. It also counts + as the successor of the GNU Library Public License, version 2, hence + the version number 2.1.] + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. + + This license, the Lesser General Public License, applies to some +specially designated software packages--typically libraries--of the +Free Software Foundation and other authors who decide to use it. You +can use it too, but we suggest you first think carefully about whether +this license or the ordinary General Public License is the better +strategy to use in any particular case, based on the explanations below. + + When we speak of free software, we are referring to freedom of use, +not price. Our General Public Licenses are designed to make sure that +you have the freedom to distribute copies of free software (and charge +for this service if you wish); that you receive source code or can get +it if you want it; that you can change the software and use pieces of +it in new free programs; and that you are informed that you can do +these things. + + To protect your rights, we need to make restrictions that forbid +distributors to deny you these rights or to ask you to surrender these +rights. These restrictions translate to certain responsibilities for +you if you distribute copies of the library or if you modify it. + + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link other code with the library, you must provide +complete object files to the recipients, so that they can relink them +with the library after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. + + We protect your rights with a two-step method: (1) we copyright the +library, and (2) we offer you this license, which gives you legal +permission to copy, distribute and/or modify the library. + + To protect each distributor, we want to make it very clear that +there is no warranty for the free library. Also, if the library is +modified by someone else and passed on, the recipients should know +that what they have is not the original version, so that the original +author's reputation will not be affected by problems that might be +introduced by others. + + Finally, software patents pose a constant threat to the existence of +any free program. We wish to make sure that a company cannot +effectively restrict the users of a free program by obtaining a +restrictive license from a patent holder. Therefore, we insist that +any patent license obtained for a version of the library must be +consistent with the full freedom of use specified in this license. + + Most GNU software, including some libraries, is covered by the +ordinary GNU General Public License. This license, the GNU Lesser +General Public License, applies to certain designated libraries, and +is quite different from the ordinary General Public License. We use +this license for certain libraries in order to permit linking those +libraries into non-free programs. + + When a program is linked with a library, whether statically or using +a shared library, the combination of the two is legally speaking a +combined work, a derivative of the original library. The ordinary +General Public License therefore permits such linking only if the +entire combination fits its criteria of freedom. The Lesser General +Public License permits more lax criteria for linking other code with +the library. + + We call this license the "Lesser" General Public License because it +does Less to protect the user's freedom than the ordinary General +Public License. It also provides other free software developers Less +of an advantage over competing non-free programs. These disadvantages +are the reason we use the ordinary General Public License for many +libraries. However, the Lesser license provides advantages in certain +special circumstances. + + For example, on rare occasions, there may be a special need to +encourage the widest possible use of a certain library, so that it becomes +a de-facto standard. To achieve this, non-free programs must be +allowed to use the library. A more frequent case is that a free +library does the same job as widely used non-free libraries. In this +case, there is little to gain by limiting the free library to free +software only, so we use the Lesser General Public License. + + In other cases, permission to use a particular library in non-free +programs enables a greater number of people to use a large body of +free software. For example, permission to use the GNU C Library in +non-free programs enables many more people to use the whole GNU +operating system, as well as its variant, the GNU/Linux operating +system. + + Although the Lesser General Public License is Less protective of the +users' freedom, it does ensure that the user of a program that is +linked with the Library has the freedom and the wherewithal to run +that program using a modified version of the Library. + + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, whereas the latter must +be combined with the library in order to run. + + GNU LESSER GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License Agreement applies to any software library or other +program which contains a notice placed by the copyright holder or +other authorized party saying it may be distributed under the terms of +this Lesser General Public License (also called "this License"). +Each licensee is addressed as "you". + + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. + + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) + + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control compilation +and installation of the library. + + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + + 1. You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. + + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. + + 2. You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) The modified work must itself be a software library. + + b) You must cause the files modified to carry prominent notices + stating that you changed the files and the date of any change. + + c) You must cause the whole of the work to be licensed at no + charge to all third parties under the terms of this License. + + d) If a facility in the modified Library refers to a function or a + table of data to be supplied by an application program that uses + the facility, other than as an argument passed when the facility + is invoked, then you must make a good faith effort to ensure that, + in the event an application does not supply such function or + table, the facility still operates, and performs whatever part of + its purpose remains meaningful. + + (For example, a function in a library to compute square roots has + a purpose that is entirely well-defined independent of the + application. Therefore, Subsection 2d requires that any + application-supplied function or table used by this function must + be optional: if the application does not supply it, the square + root function must still compute square roots.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. + +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. + + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. + + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. + + 4. You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. + + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. + + 5. A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. + + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. + + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. + + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) + + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. + + 6. As an exception to the Sections above, you may also combine or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. + + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: + + a) Accompany the work with the complete corresponding + machine-readable source code for the Library including whatever + changes were used in the work (which must be distributed under + Sections 1 and 2 above); and, if the work is an executable linked + with the Library, with the complete machine-readable "work that + uses the Library", as object code and/or source code, so that the + user can modify the Library and then relink to produce a modified + executable containing the modified Library. (It is understood + that the user who changes the contents of definitions files in the + Library will not necessarily be able to recompile the application + to use the modified definitions.) + + b) Use a suitable shared library mechanism for linking with the + Library. A suitable mechanism is one that (1) uses at run time a + copy of the library already present on the user's computer system, + rather than copying library functions into the executable, and (2) + will operate properly with a modified version of the library, if + the user installs one, as long as the modified version is + interface-compatible with the version that the work was made with. + + c) Accompany the work with a written offer, valid for at + least three years, to give the same user the materials + specified in Subsection 6a, above, for a charge no more + than the cost of performing this distribution. + + d) If distribution of the work is made by offering access to copy + from a designated place, offer equivalent access to copy the above + specified materials from the same place. + + e) Verify that the user has already received a copy of these + materials or that you have already sent this user a copy. + + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the materials to be distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. + + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. + + 7. You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: + + a) Accompany the combined library with a copy of the same work + based on the Library, uncombined with any other library + facilities. This must be distributed under the terms of the + Sections above. + + b) Give prominent notice with the combined library of the fact + that part of it is a work based on the Library, and explaining + where to find the accompanying uncombined form of the same work. + + 8. You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. + + 9. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. + + 10. Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties with +this License. + + 11. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. + +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 12. If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. + + 13. The Free Software Foundation may publish revised and/or new +versions of the Lesser General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. + + 14. If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. + + NO WARRANTY + + 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Libraries + + If you develop a new library, and you want it to be of the greatest +possible use to the public, we recommend making it free software that +everyone can redistribute and change. You can do so by permitting +redistribution under these terms (or, alternatively, under the terms of the +ordinary General Public License). + + To apply these terms, attach the following notices to the library. It is +safest to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least the +"copyright" line and a pointer to where the full notice is found. + + + Copyright (C) + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + +Also add information on how to contact you by electronic and paper mail. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the library, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the + library `Frob' (a library for tweaking knobs) written by James Random Hacker. + + , 1 April 1990 + Ty Coon, President of Vice + +That's all there is to it! + + diff --git a/test_rwlock_timing.c b/test_rwlock_timing.c index 2c3d894..2c45658 100644 --- a/test_rwlock_timing.c +++ b/test_rwlock_timing.c @@ -5,7 +5,19 @@ * * Copyright February 2009 - Mathieu Desnoyers * - * Distributed under GPLv2 + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ #include diff --git a/test_urcu.c b/test_urcu.c index a044d53..72cceeb 100644 --- a/test_urcu.c +++ b/test_urcu.c @@ -5,7 +5,19 @@ * * Copyright February 2009 - Mathieu Desnoyers * - * Distributed under GPLv2 + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ #include diff --git a/test_urcu_timing.c b/test_urcu_timing.c index a11532a..cf70709 100644 --- a/test_urcu_timing.c +++ b/test_urcu_timing.c @@ -5,7 +5,19 @@ * * Copyright February 2009 - Mathieu Desnoyers * - * Distributed under GPLv2 + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ #include diff --git a/urcu.c b/urcu.c index 7ab87c4..8fd6195 100644 --- a/urcu.c +++ b/urcu.c @@ -3,9 +3,22 @@ * * Userspace RCU library * - * Copyright February 2009 - Mathieu Desnoyers + * Copyright (c) 2009 Mathieu Desnoyers + * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. * - * Distributed under LGPLv2.1 + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * * IBM's contributions to this file may be relicensed under LGPLv2 or later. */ diff --git a/urcu.h b/urcu.h index 0b0d232..b46033f 100644 --- a/urcu.h +++ b/urcu.h @@ -6,17 +6,27 @@ * * Userspace RCU header * - * Copyright February 2009 - Mathieu Desnoyers - * - * Credits for Paul E. McKenney - * for inspiration coming from the Linux kernel RCU and rcu-preempt. + * Copyright (c) 2009 Mathieu Desnoyers + * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. * * LGPL-compatible code should include this header with : * * #define _LGPL_SOURCE * #include * - * Distributed under LGPLv2.1 + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * * IBM's contributions to this file may be relicensed under LGPLv2 or later. */ -- 2.34.1 From adcfce542ec1c28796c3c641021a6d37f97b6f6f Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 10 May 2009 22:20:47 -0400 Subject: [PATCH 08/16] Add missing urcu-static.h This new file should be inly included in LGPL-compatible code. Signed-off-by: Mathieu Desnoyers --- urcu-static.h | 277 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 277 insertions(+) create mode 100644 urcu-static.h diff --git a/urcu-static.h b/urcu-static.h new file mode 100644 index 0000000..c47a759 --- /dev/null +++ b/urcu-static.h @@ -0,0 +1,277 @@ +#ifndef _URCU_STATIC_H +#define _URCU_STATIC_H + +/* + * urcu-static.h + * + * Userspace RCU header, to be included only in LGPL-compatible code. + * + * Copyright February 2009 - Mathieu Desnoyers + * + * Credits for Paul E. McKenney + * for inspiration coming from the Linux kernel RCU and rcu-preempt. + * + * Distributed under LGPLv2.1 + * + * IBM's contributions to this file may be relicensed under LGPLv2 or later. + */ + +#include +#include + +#include +#include + +/* + * Identify a shared load. A smp_rmc() or smp_mc() should come before the load. + */ +#define _LOAD_SHARED(p) ACCESS_ONCE(p) + +/* + * Load a data from shared memory, doing a cache flush if required. + */ +#define LOAD_SHARED(p) \ + ({ \ + smp_rmc(); \ + _LOAD_SHARED(p); \ + }) + +/* + * Identify a shared store. A smp_wmc() or smp_mc() should follow the store. + */ +#define _STORE_SHARED(x, v) ({ ACCESS_ONCE(x) = (v); }) + +/* + * Store v into x, where x is located in shared memory. Performs the required + * cache flush after writing. Returns v. + */ +#define STORE_SHARED(x, v) \ + ({ \ + _STORE_SHARED(x, v); \ + smp_wmc(); \ + (v); \ + }) + +/** + * _rcu_dereference - reads (copy) a RCU-protected pointer to a local variable + * into a RCU read-side critical section. The pointer can later be safely + * dereferenced within the critical section. + * + * This ensures that the pointer copy is invariant thorough the whole critical + * section. + * + * Inserts memory barriers on architectures that require them (currently only + * Alpha) and documents which pointers are protected by RCU. + * + * Should match rcu_assign_pointer() or rcu_xchg_pointer(). + */ + +#define _rcu_dereference(p) ({ \ + typeof(p) _________p1 = LOAD_SHARED(p); \ + smp_read_barrier_depends(); \ + (_________p1); \ + }) + +/* + * This code section can only be included in LGPL 2.1 compatible source code. + * See below for the function call wrappers which can be used in code meant to + * be only linked with the Userspace RCU library. This comes with a small + * performance degradation on the read-side due to the added function calls. + * This is required to permit relinking with newer versions of the library. + */ + +/* + * The signal number used by the RCU library can be overridden with + * -DSIGURCU= when compiling the library. + */ +#ifndef SIGURCU +#define SIGURCU SIGUSR1 +#endif + +/* + * If a reader is really non-cooperative and refuses to commit its + * urcu_active_readers count to memory (there is no barrier in the reader + * per-se), kick it after a few loops waiting for it. + */ +#define KICK_READER_LOOPS 10000 + +#ifdef DEBUG_YIELD +#include +#include +#include +#include + +#define YIELD_READ (1 << 0) +#define YIELD_WRITE (1 << 1) + +/* Updates without DEBUG_FULL_MB are much slower. Account this in the delay */ +#ifdef DEBUG_FULL_MB +/* maximum sleep delay, in us */ +#define MAX_SLEEP 50 +#else +#define MAX_SLEEP 30000 +#endif + +extern unsigned int yield_active; +extern unsigned int __thread rand_yield; + +static inline void debug_yield_read(void) +{ + if (yield_active & YIELD_READ) + if (rand_r(&rand_yield) & 0x1) + usleep(rand_r(&rand_yield) % MAX_SLEEP); +} + +static inline void debug_yield_write(void) +{ + if (yield_active & YIELD_WRITE) + if (rand_r(&rand_yield) & 0x1) + usleep(rand_r(&rand_yield) % MAX_SLEEP); +} + +static inline void debug_yield_init(void) +{ + rand_yield = time(NULL) ^ pthread_self(); +} +#else +static inline void debug_yield_read(void) +{ +} + +static inline void debug_yield_write(void) +{ +} + +static inline void debug_yield_init(void) +{ + +} +#endif + +#ifdef DEBUG_FULL_MB +static inline void reader_barrier() +{ + smp_mb(); +} +#else +static inline void reader_barrier() +{ + barrier(); +} +#endif + +/* + * The trick here is that RCU_GP_CTR_BIT must be a multiple of 8 so we can use a + * full 8-bits, 16-bits or 32-bits bitmask for the lower order bits. + */ +#define RCU_GP_COUNT (1UL << 0) +/* Use the amount of bits equal to half of the architecture long size */ +#define RCU_GP_CTR_BIT (1UL << (sizeof(long) << 2)) +#define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BIT - 1) + +/* + * Global quiescent period counter with low-order bits unused. + * Using a int rather than a char to eliminate false register dependencies + * causing stalls on some architectures. + */ +extern long urcu_gp_ctr; + +extern long __thread urcu_active_readers; + +static inline int rcu_old_gp_ongoing(long *value) +{ + long v; + + if (value == NULL) + return 0; + /* + * Make sure both tests below are done on the same version of *value + * to insure consistency. + */ + v = LOAD_SHARED(*value); + return (v & RCU_GP_CTR_NEST_MASK) && + ((v ^ urcu_gp_ctr) & RCU_GP_CTR_BIT); +} + +static inline void _rcu_read_lock(void) +{ + long tmp; + + tmp = urcu_active_readers; + /* urcu_gp_ctr = RCU_GP_COUNT | (~RCU_GP_CTR_BIT or RCU_GP_CTR_BIT) */ + /* + * The data dependency "read urcu_gp_ctr, write urcu_active_readers", + * serializes those two memory operations. The memory barrier in the + * signal handler ensures we receive the proper memory commit barriers + * required by _STORE_SHARED and _LOAD_SHARED whenever communication + * with the writer is needed. + */ + if (likely(!(tmp & RCU_GP_CTR_NEST_MASK))) + _STORE_SHARED(urcu_active_readers, _LOAD_SHARED(urcu_gp_ctr)); + else + _STORE_SHARED(urcu_active_readers, tmp + RCU_GP_COUNT); + /* + * Increment active readers count before accessing the pointer. + * See force_mb_all_threads(). + */ + reader_barrier(); +} + +static inline void _rcu_read_unlock(void) +{ + reader_barrier(); + /* + * Finish using rcu before decrementing the pointer. + * See force_mb_all_threads(). + */ + _STORE_SHARED(urcu_active_readers, urcu_active_readers - RCU_GP_COUNT); +} + +/** + * _rcu_assign_pointer - assign (publicize) a pointer to a new data structure + * meant to be read by RCU read-side critical sections. Returns the assigned + * value. + * + * Documents which pointers will be dereferenced by RCU read-side critical + * sections and adds the required memory barriers on architectures requiring + * them. It also makes sure the compiler does not reorder code initializing the + * data structure before its publication. + * + * Should match rcu_dereference_pointer(). + */ + +#define _rcu_assign_pointer(p, v) \ + ({ \ + if (!__builtin_constant_p(v) || \ + ((v) != NULL)) \ + wmb(); \ + STORE_SHARED(p, v); \ + }) + +/** + * _rcu_xchg_pointer - same as rcu_assign_pointer, but returns the previous + * pointer to the data structure, which can be safely freed after waitin for a + * quiescent state using synchronize_rcu(). + */ + +#define _rcu_xchg_pointer(p, v) \ + ({ \ + if (!__builtin_constant_p(v) || \ + ((v) != NULL)) \ + wmb(); \ + xchg(p, v); \ + }) + +/* + * Exchanges the pointer and waits for quiescent state. + * The pointer returned can be freed. + */ +#define _rcu_publish_content(p, v) \ + ({ \ + void *oldptr; \ + oldptr = _rcu_xchg_pointer(p, v); \ + synchronize_rcu(); \ + oldptr; \ + }) + +#endif /* _URCU_STATIC_H */ -- 2.34.1 From 5e116f1361ab64e6a41459a8f01c80131f79a8a2 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 10 May 2009 22:22:02 -0400 Subject: [PATCH 09/16] Remove automatically generated api.h from repository Signed-off-by: Mathieu Desnoyers --- api.h | 1432 --------------------------------------------------------- 1 file changed, 1432 deletions(-) delete mode 100644 api.h diff --git a/api.h b/api.h deleted file mode 100644 index 8bc52e8..0000000 --- a/api.h +++ /dev/null @@ -1,1432 +0,0 @@ -/* MECHANICALLY GENERATED, DO NOT EDIT!!! */ - -#define _INCLUDE_API_H - -/* - * common.h: Common Linux kernel-isms. - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; but version 2 of the License only due - * to code included from the Linux kernel. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - * - * Copyright (c) 2006 Paul E. McKenney, IBM. - * - * Much code taken from the Linux kernel. For such code, the option - * to redistribute under later versions of GPL might not be available. - */ - -#ifndef __always_inline -#define __always_inline inline -#endif - -#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)])) -#define BUILD_BUG_ON_ZERO(e) (sizeof(char[1 - 2 * !!(e)]) - 1) - -#ifdef __ASSEMBLY__ -# define stringify_in_c(...) __VA_ARGS__ -# define ASM_CONST(x) x -#else -/* This version of stringify will deal with commas... */ -# define __stringify_in_c(...) #__VA_ARGS__ -# define stringify_in_c(...) __stringify_in_c(__VA_ARGS__) " " -# define __ASM_CONST(x) x##UL -# define ASM_CONST(x) __ASM_CONST(x) -#endif - - -/* - * arch-i386.h: Expose x86 atomic instructions. 80486 and better only. - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, but version 2 only due to inclusion - * of Linux-kernel code. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - * - * Copyright (c) 2006 Paul E. McKenney, IBM. - * - * Much code taken from the Linux kernel. For such code, the option - * to redistribute under later versions of GPL might not be available. - */ - -/* - * Machine parameters. - */ - -#define CONFIG_SMP - -#define CACHE_LINE_SIZE 64 -#define ____cacheline_internodealigned_in_smp \ - __attribute__((__aligned__(1 << 6))) - -#define LOCK_PREFIX "lock ; " - -/* - * Atomic data structure, initialization, and access. - */ - -typedef struct { volatile int counter; } atomic_t; - -#define ATOMIC_INIT(i) { (i) } - -#define atomic_read(v) ((v)->counter) -#define atomic_set(v, i) (((v)->counter) = (i)) - -/* - * Atomic operations. - */ - -/** - * atomic_add - add integer to atomic variable - * @i: integer value to add - * @v: pointer of type atomic_t - * - * Atomically adds @i to @v. - */ -static __inline__ void atomic_add(int i, atomic_t *v) -{ - __asm__ __volatile__( - LOCK_PREFIX "addl %1,%0" - :"+m" (v->counter) - :"ir" (i)); -} - -/** - * atomic_sub - subtract the atomic variable - * @i: integer value to subtract - * @v: pointer of type atomic_t - * - * Atomically subtracts @i from @v. - */ -static __inline__ void atomic_sub(int i, atomic_t *v) -{ - __asm__ __volatile__( - LOCK_PREFIX "subl %1,%0" - :"+m" (v->counter) - :"ir" (i)); -} - -/** - * atomic_sub_and_test - subtract value from variable and test result - * @i: integer value to subtract - * @v: pointer of type atomic_t - * - * Atomically subtracts @i from @v and returns - * true if the result is zero, or false for all - * other cases. - */ -static __inline__ int atomic_sub_and_test(int i, atomic_t *v) -{ - unsigned char c; - - __asm__ __volatile__( - LOCK_PREFIX "subl %2,%0; sete %1" - :"+m" (v->counter), "=qm" (c) - :"ir" (i) : "memory"); - return c; -} - -/** - * atomic_inc - increment atomic variable - * @v: pointer of type atomic_t - * - * Atomically increments @v by 1. - */ -static __inline__ void atomic_inc(atomic_t *v) -{ - __asm__ __volatile__( - LOCK_PREFIX "incl %0" - :"+m" (v->counter)); -} - -/** - * atomic_dec - decrement atomic variable - * @v: pointer of type atomic_t - * - * Atomically decrements @v by 1. - */ -static __inline__ void atomic_dec(atomic_t *v) -{ - __asm__ __volatile__( - LOCK_PREFIX "decl %0" - :"+m" (v->counter)); -} - -/** - * atomic_dec_and_test - decrement and test - * @v: pointer of type atomic_t - * - * Atomically decrements @v by 1 and - * returns true if the result is 0, or false for all other - * cases. - */ -static __inline__ int atomic_dec_and_test(atomic_t *v) -{ - unsigned char c; - - __asm__ __volatile__( - LOCK_PREFIX "decl %0; sete %1" - :"+m" (v->counter), "=qm" (c) - : : "memory"); - return c != 0; -} - -/** - * atomic_inc_and_test - increment and test - * @v: pointer of type atomic_t - * - * Atomically increments @v by 1 - * and returns true if the result is zero, or false for all - * other cases. - */ -static __inline__ int atomic_inc_and_test(atomic_t *v) -{ - unsigned char c; - - __asm__ __volatile__( - LOCK_PREFIX "incl %0; sete %1" - :"+m" (v->counter), "=qm" (c) - : : "memory"); - return c != 0; -} - -/** - * atomic_add_negative - add and test if negative - * @v: pointer of type atomic_t - * @i: integer value to add - * - * Atomically adds @i to @v and returns true - * if the result is negative, or false when - * result is greater than or equal to zero. - */ -static __inline__ int atomic_add_negative(int i, atomic_t *v) -{ - unsigned char c; - - __asm__ __volatile__( - LOCK_PREFIX "addl %2,%0; sets %1" - :"+m" (v->counter), "=qm" (c) - :"ir" (i) : "memory"); - return c; -} - -/** - * atomic_add_return - add and return - * @v: pointer of type atomic_t - * @i: integer value to add - * - * Atomically adds @i to @v and returns @i + @v - */ -static __inline__ int atomic_add_return(int i, atomic_t *v) -{ - int __i; - - __i = i; - __asm__ __volatile__( - LOCK_PREFIX "xaddl %0, %1;" - :"=r"(i) - :"m"(v->counter), "0"(i)); - return i + __i; -} - -static __inline__ int atomic_sub_return(int i, atomic_t *v) -{ - return atomic_add_return(-i,v); -} - -static inline unsigned int -cmpxchg(volatile long *ptr, long oldval, long newval) -{ - unsigned long retval; - - asm("# cmpxchg\n" - "lock; cmpxchgl %4,(%2)\n" - "# end atomic_cmpxchg4" - : "=a" (retval), "=m" (*ptr) - : "r" (ptr), "0" (oldval), "r" (newval), "m" (*ptr) - : "cc"); - return (retval); -} - -#define atomic_cmpxchg(v, old, new) ((int)cmpxchg(&((v)->counter), old, new)) -#define atomic_xchg(v, new) (xchg(&((v)->counter), new)) - -/** - * atomic_add_unless - add unless the number is a given value - * @v: pointer of type atomic_t - * @a: the amount to add to v... - * @u: ...unless v is equal to u. - * - * Atomically adds @a to @v, so long as it was not @u. - * Returns non-zero if @v was not @u, and zero otherwise. - */ -#define atomic_add_unless(v, a, u) \ -({ \ - int c, old; \ - c = atomic_read(v); \ - for (;;) { \ - if (unlikely(c == (u))) \ - break; \ - old = atomic_cmpxchg((v), c, c + (a)); \ - if (likely(old == c)) \ - break; \ - c = old; \ - } \ - c != (u); \ -}) -#define atomic_inc_not_zero(v) atomic_add_unless((v), 1, 0) - -#define atomic_inc_return(v) (atomic_add_return(1,v)) -#define atomic_dec_return(v) (atomic_sub_return(1,v)) - -/* These are x86-specific, used by some header files */ -#define atomic_clear_mask(mask, addr) \ -__asm__ __volatile__(LOCK_PREFIX "andl %0,%1" \ -: : "r" (~(mask)),"m" (*addr) : "memory") - -#define atomic_set_mask(mask, addr) \ -__asm__ __volatile__(LOCK_PREFIX "orl %0,%1" \ -: : "r" (mask),"m" (*(addr)) : "memory") - -/* Atomic operations are already serializing on x86 */ -#define smp_mb__before_atomic_dec() barrier() -#define smp_mb__after_atomic_dec() barrier() -#define smp_mb__before_atomic_inc() barrier() -#define smp_mb__after_atomic_inc() barrier() - -#define smp_mb() \ -__asm__ __volatile__("mfence" : : : "memory") -/* __asm__ __volatile__("lock; addl $0,0(%%esp)" : : : "memory") */ - - -/* - * Generate 64-bit timestamp. - */ - -static unsigned long long get_timestamp(void) -{ - unsigned int __a,__d; - - __asm__ __volatile__("rdtsc" : "=a" (__a), "=d" (__d)); - return ((long long)__a) | (((long long)__d)<<32); -} - -/* - * api_pthreads.h: API mapping to pthreads environment. - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. However, please note that much - * of the code in this file derives from the Linux kernel, and that such - * code may not be available except under GPLv2. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - * - * Copyright (c) 2006 Paul E. McKenney, IBM. - */ - -#include -#include -#include -#include -#include -#define __USE_GNU -#include -#include -#include -/* #include "atomic.h" */ - -/* - * Compiler magic. - */ -#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) -#define container_of(ptr, type, member) ({ \ - const typeof( ((type *)0)->member ) *__mptr = (ptr); \ - (type *)( (char *)__mptr - offsetof(type,member) );}) -#define barrier() __asm__ __volatile__("": : :"memory") - -/* - * Default machine parameters. - */ - -#ifndef CACHE_LINE_SIZE -#define CACHE_LINE_SIZE 128 -#endif /* #ifndef CACHE_LINE_SIZE */ - -/* - * Exclusive locking primitives. - */ - -typedef pthread_mutex_t spinlock_t; - -#define DEFINE_SPINLOCK(lock) spinlock_t lock = PTHREAD_MUTEX_INITIALIZER; -#define __SPIN_LOCK_UNLOCKED(lockp) PTHREAD_MUTEX_INITIALIZER - -static void spin_lock_init(spinlock_t *sp) -{ - if (pthread_mutex_init(sp, NULL) != 0) { - perror("spin_lock_init:pthread_mutex_init"); - exit(-1); - } -} - -static void spin_lock(spinlock_t *sp) -{ - if (pthread_mutex_lock(sp) != 0) { - perror("spin_lock:pthread_mutex_lock"); - exit(-1); - } -} - -static int spin_trylock(spinlock_t *sp) -{ - int retval; - - if ((retval = pthread_mutex_trylock(sp)) == 0) - return 1; - if (retval == EBUSY) - return 0; - perror("spin_trylock:pthread_mutex_trylock"); - exit(-1); -} - -static void spin_unlock(spinlock_t *sp) -{ - if (pthread_mutex_unlock(sp) != 0) { - perror("spin_unlock:pthread_mutex_unlock"); - exit(-1); - } -} - -#define spin_lock_irqsave(l, f) do { f = 1; spin_lock(l); } while (0) -#define spin_unlock_irqrestore(l, f) do { f = 0; spin_unlock(l); } while (0) - -#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x)) -#define unlikely(x) x -#define likely(x) x -#define prefetch(x) x - -/* - * Thread creation/destruction primitives. - */ - -typedef pthread_t thread_id_t; - -#define NR_THREADS 128 - -#define __THREAD_ID_MAP_EMPTY 0 -#define __THREAD_ID_MAP_WAITING 1 -thread_id_t __thread_id_map[NR_THREADS]; -spinlock_t __thread_id_map_mutex; - -#define for_each_thread(t) \ - for (t = 0; t < NR_THREADS; t++) - -#define for_each_running_thread(t) \ - for (t = 0; t < NR_THREADS; t++) \ - if ((__thread_id_map[t] != __THREAD_ID_MAP_EMPTY) && \ - (__thread_id_map[t] != __THREAD_ID_MAP_WAITING)) - -pthread_key_t thread_id_key; - -static int __smp_thread_id(void) -{ - int i; - thread_id_t tid = pthread_self(); - - for (i = 0; i < NR_THREADS; i++) { - if (__thread_id_map[i] == tid) { - long v = i + 1; /* must be non-NULL. */ - - if (pthread_setspecific(thread_id_key, (void *)v) != 0) { - perror("pthread_setspecific"); - exit(-1); - } - return i; - } - } - spin_lock(&__thread_id_map_mutex); - for (i = 0; i < NR_THREADS; i++) { - if (__thread_id_map[i] == tid) - spin_unlock(&__thread_id_map_mutex); - return i; - } - spin_unlock(&__thread_id_map_mutex); - fprintf(stderr, "smp_thread_id: Rogue thread, id: %d(%#x)\n", tid, tid); - exit(-1); -} - -static int smp_thread_id(void) -{ - void *id; - - id = pthread_getspecific(thread_id_key); - if (id == NULL) - return __smp_thread_id(); - return (long)(id - 1); -} - -static thread_id_t create_thread(void *(*func)(void *), void *arg) -{ - thread_id_t tid; - int i; - - spin_lock(&__thread_id_map_mutex); - for (i = 0; i < NR_THREADS; i++) { - if (__thread_id_map[i] == __THREAD_ID_MAP_EMPTY) - break; - } - if (i >= NR_THREADS) { - spin_unlock(&__thread_id_map_mutex); - fprintf(stderr, "Thread limit of %d exceeded!\n", NR_THREADS); - exit(-1); - } - __thread_id_map[i] = __THREAD_ID_MAP_WAITING; - spin_unlock(&__thread_id_map_mutex); - if (pthread_create(&tid, NULL, func, arg) != 0) { - perror("create_thread:pthread_create"); - exit(-1); - } - __thread_id_map[i] = tid; - return tid; -} - -static void *wait_thread(thread_id_t tid) -{ - int i; - void *vp; - - for (i = 0; i < NR_THREADS; i++) { - if (__thread_id_map[i] == tid) - break; - } - if (i >= NR_THREADS){ - fprintf(stderr, "wait_thread: bad tid = %d(%#x)\n", tid, tid); - exit(-1); - } - if (pthread_join(tid, &vp) != 0) { - perror("wait_thread:pthread_join"); - exit(-1); - } - __thread_id_map[i] = __THREAD_ID_MAP_EMPTY; - return vp; -} - -static void wait_all_threads(void) -{ - int i; - thread_id_t tid; - - for (i = 1; i < NR_THREADS; i++) { - tid = __thread_id_map[i]; - if (tid != __THREAD_ID_MAP_EMPTY && - tid != __THREAD_ID_MAP_WAITING) - (void)wait_thread(tid); - } -} - -static void run_on(int cpu) -{ - cpu_set_t mask; - - CPU_ZERO(&mask); - CPU_SET(cpu, &mask); - sched_setaffinity(0, sizeof(mask), &mask); -} - -/* - * timekeeping -- very crude -- should use MONOTONIC... - */ - -long long get_microseconds(void) -{ - struct timeval tv; - - if (gettimeofday(&tv, NULL) != 0) - abort(); - return ((long long)tv.tv_sec) * 1000000LL + (long long)tv.tv_usec; -} - -/* - * Per-thread variables. - */ - -#define DEFINE_PER_THREAD(type, name) \ - struct { \ - __typeof__(type) v \ - __attribute__((__aligned__(CACHE_LINE_SIZE))); \ - } __per_thread_##name[NR_THREADS]; -#define DECLARE_PER_THREAD(type, name) extern DEFINE_PER_THREAD(type, name) - -#define per_thread(name, thread) __per_thread_##name[thread].v -#define __get_thread_var(name) per_thread(name, smp_thread_id()) - -#define init_per_thread(name, v) \ - do { \ - int __i_p_t_i; \ - for (__i_p_t_i = 0; __i_p_t_i < NR_THREADS; __i_p_t_i++) \ - per_thread(name, __i_p_t_i) = v; \ - } while (0) - -/* - * CPU traversal primitives. - */ - -#ifndef NR_CPUS -#define NR_CPUS 16 -#endif /* #ifndef NR_CPUS */ - -#define for_each_possible_cpu(cpu) \ - for (cpu = 0; cpu < NR_CPUS; cpu++) -#define for_each_online_cpu(cpu) \ - for (cpu = 0; cpu < NR_CPUS; cpu++) - -/* - * Per-CPU variables. - */ - -#define DEFINE_PER_CPU(type, name) \ - struct { \ - __typeof__(type) v \ - __attribute__((__aligned__(CACHE_LINE_SIZE))); \ - } __per_cpu_##name[NR_CPUS] -#define DECLARE_PER_CPU(type, name) extern DEFINE_PER_CPU(type, name) - -DEFINE_PER_THREAD(int, smp_processor_id); - -static int smp_processor_id(void) -{ - return __get_thread_var(smp_processor_id); -} - -static void set_smp_processor_id(int cpu) -{ - __get_thread_var(smp_processor_id) = cpu; -} - -#define per_cpu(name, thread) __per_cpu_##name[thread].v -#define __get_cpu_var(name) per_cpu(name, smp_processor_id()) - -#define init_per_cpu(name, v) \ - do { \ - int __i_p_c_i; \ - for (__i_p_c_i = 0; __i_p_c_i < NR_CPUS; __i_p_c_i++) \ - per_cpu(name, __i_p_c_i) = v; \ - } while (0) - -/* - * CPU state checking (crowbarred). - */ - -#define idle_cpu(cpu) 0 -#define in_softirq() 1 -#define hardirq_count() 0 -#define PREEMPT_SHIFT 0 -#define SOFTIRQ_SHIFT (PREEMPT_SHIFT + PREEMPT_BITS) -#define HARDIRQ_SHIFT (SOFTIRQ_SHIFT + SOFTIRQ_BITS) -#define PREEMPT_BITS 8 -#define SOFTIRQ_BITS 8 - -/* - * CPU hotplug. - */ - -struct notifier_block { - int (*notifier_call)(struct notifier_block *, unsigned long, void *); - struct notifier_block *next; - int priority; -}; - -#define CPU_ONLINE 0x0002 /* CPU (unsigned)v is up */ -#define CPU_UP_PREPARE 0x0003 /* CPU (unsigned)v coming up */ -#define CPU_UP_CANCELED 0x0004 /* CPU (unsigned)v NOT coming up */ -#define CPU_DOWN_PREPARE 0x0005 /* CPU (unsigned)v going down */ -#define CPU_DOWN_FAILED 0x0006 /* CPU (unsigned)v NOT going down */ -#define CPU_DEAD 0x0007 /* CPU (unsigned)v dead */ -#define CPU_DYING 0x0008 /* CPU (unsigned)v not running any task, - * not handling interrupts, soon dead */ -#define CPU_POST_DEAD 0x0009 /* CPU (unsigned)v dead, cpu_hotplug - * lock is dropped */ - -/* Used for CPU hotplug events occuring while tasks are frozen due to a suspend - * operation in progress - */ -#define CPU_TASKS_FROZEN 0x0010 - -#define CPU_ONLINE_FROZEN (CPU_ONLINE | CPU_TASKS_FROZEN) -#define CPU_UP_PREPARE_FROZEN (CPU_UP_PREPARE | CPU_TASKS_FROZEN) -#define CPU_UP_CANCELED_FROZEN (CPU_UP_CANCELED | CPU_TASKS_FROZEN) -#define CPU_DOWN_PREPARE_FROZEN (CPU_DOWN_PREPARE | CPU_TASKS_FROZEN) -#define CPU_DOWN_FAILED_FROZEN (CPU_DOWN_FAILED | CPU_TASKS_FROZEN) -#define CPU_DEAD_FROZEN (CPU_DEAD | CPU_TASKS_FROZEN) -#define CPU_DYING_FROZEN (CPU_DYING | CPU_TASKS_FROZEN) - -/* Hibernation and suspend events */ -#define PM_HIBERNATION_PREPARE 0x0001 /* Going to hibernate */ -#define PM_POST_HIBERNATION 0x0002 /* Hibernation finished */ -#define PM_SUSPEND_PREPARE 0x0003 /* Going to suspend the system */ -#define PM_POST_SUSPEND 0x0004 /* Suspend finished */ -#define PM_RESTORE_PREPARE 0x0005 /* Going to restore a saved image */ -#define PM_POST_RESTORE 0x0006 /* Restore failed */ - -#define NOTIFY_DONE 0x0000 /* Don't care */ -#define NOTIFY_OK 0x0001 /* Suits me */ -#define NOTIFY_STOP_MASK 0x8000 /* Don't call further */ -#define NOTIFY_BAD (NOTIFY_STOP_MASK|0x0002) - /* Bad/Veto action */ -/* - * Clean way to return from the notifier and stop further calls. - */ -#define NOTIFY_STOP (NOTIFY_OK|NOTIFY_STOP_MASK) - -/* - * Bug checks. - */ - -#define BUG_ON(c) do { if (!(c)) abort(); } while (0) - -/* - * Initialization -- Must be called before calling any primitives. - */ - -static void smp_init(void) -{ - int i; - - spin_lock_init(&__thread_id_map_mutex); - __thread_id_map[0] = pthread_self(); - for (i = 1; i < NR_THREADS; i++) - __thread_id_map[i] = __THREAD_ID_MAP_EMPTY; - init_per_thread(smp_processor_id, 0); - if (pthread_key_create(&thread_id_key, NULL) != 0) { - perror("pthread_key_create"); - exit(-1); - } -} - -/* Taken from the Linux kernel source tree, so GPLv2-only!!! */ - -#ifndef _LINUX_LIST_H -#define _LINUX_LIST_H - -#define LIST_POISON1 ((void *) 0x00100100) -#define LIST_POISON2 ((void *) 0x00200200) - -#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) -#define container_of(ptr, type, member) ({ \ - const typeof( ((type *)0)->member ) *__mptr = (ptr); \ - (type *)( (char *)__mptr - offsetof(type,member) );}) - -/* - * Simple doubly linked list implementation. - * - * Some of the internal functions ("__xxx") are useful when - * manipulating whole lists rather than single entries, as - * sometimes we already know the next/prev entries and we can - * generate better code by using them directly rather than - * using the generic single-entry routines. - */ - -struct list_head { - struct list_head *next, *prev; -}; - -#define LIST_HEAD_INIT(name) { &(name), &(name) } - -#define LIST_HEAD(name) \ - struct list_head name = LIST_HEAD_INIT(name) - -static inline void INIT_LIST_HEAD(struct list_head *list) -{ - list->next = list; - list->prev = list; -} - -/* - * Insert a new entry between two known consecutive entries. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -#ifndef CONFIG_DEBUG_LIST -static inline void __list_add(struct list_head *new, - struct list_head *prev, - struct list_head *next) -{ - next->prev = new; - new->next = next; - new->prev = prev; - prev->next = new; -} -#else -extern void __list_add(struct list_head *new, - struct list_head *prev, - struct list_head *next); -#endif - -/** - * list_add - add a new entry - * @new: new entry to be added - * @head: list head to add it after - * - * Insert a new entry after the specified head. - * This is good for implementing stacks. - */ -static inline void list_add(struct list_head *new, struct list_head *head) -{ - __list_add(new, head, head->next); -} - - -/** - * list_add_tail - add a new entry - * @new: new entry to be added - * @head: list head to add it before - * - * Insert a new entry before the specified head. - * This is useful for implementing queues. - */ -static inline void list_add_tail(struct list_head *new, struct list_head *head) -{ - __list_add(new, head->prev, head); -} - -/* - * Delete a list entry by making the prev/next entries - * point to each other. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -static inline void __list_del(struct list_head * prev, struct list_head * next) -{ - next->prev = prev; - prev->next = next; -} - -/** - * list_del - deletes entry from list. - * @entry: the element to delete from the list. - * Note: list_empty() on entry does not return true after this, the entry is - * in an undefined state. - */ -#ifndef CONFIG_DEBUG_LIST -static inline void list_del(struct list_head *entry) -{ - __list_del(entry->prev, entry->next); - entry->next = LIST_POISON1; - entry->prev = LIST_POISON2; -} -#else -extern void list_del(struct list_head *entry); -#endif - -/** - * list_replace - replace old entry by new one - * @old : the element to be replaced - * @new : the new element to insert - * - * If @old was empty, it will be overwritten. - */ -static inline void list_replace(struct list_head *old, - struct list_head *new) -{ - new->next = old->next; - new->next->prev = new; - new->prev = old->prev; - new->prev->next = new; -} - -static inline void list_replace_init(struct list_head *old, - struct list_head *new) -{ - list_replace(old, new); - INIT_LIST_HEAD(old); -} - -/** - * list_del_init - deletes entry from list and reinitialize it. - * @entry: the element to delete from the list. - */ -static inline void list_del_init(struct list_head *entry) -{ - __list_del(entry->prev, entry->next); - INIT_LIST_HEAD(entry); -} - -/** - * list_move - delete from one list and add as another's head - * @list: the entry to move - * @head: the head that will precede our entry - */ -static inline void list_move(struct list_head *list, struct list_head *head) -{ - __list_del(list->prev, list->next); - list_add(list, head); -} - -/** - * list_move_tail - delete from one list and add as another's tail - * @list: the entry to move - * @head: the head that will follow our entry - */ -static inline void list_move_tail(struct list_head *list, - struct list_head *head) -{ - __list_del(list->prev, list->next); - list_add_tail(list, head); -} - -/** - * list_is_last - tests whether @list is the last entry in list @head - * @list: the entry to test - * @head: the head of the list - */ -static inline int list_is_last(const struct list_head *list, - const struct list_head *head) -{ - return list->next == head; -} - -/** - * list_empty - tests whether a list is empty - * @head: the list to test. - */ -static inline int list_empty(const struct list_head *head) -{ - return head->next == head; -} - -/** - * list_empty_careful - tests whether a list is empty and not being modified - * @head: the list to test - * - * Description: - * tests whether a list is empty _and_ checks that no other CPU might be - * in the process of modifying either member (next or prev) - * - * NOTE: using list_empty_careful() without synchronization - * can only be safe if the only activity that can happen - * to the list entry is list_del_init(). Eg. it cannot be used - * if another CPU could re-list_add() it. - */ -static inline int list_empty_careful(const struct list_head *head) -{ - struct list_head *next = head->next; - return (next == head) && (next == head->prev); -} - -/** - * list_is_singular - tests whether a list has just one entry. - * @head: the list to test. - */ -static inline int list_is_singular(const struct list_head *head) -{ - return !list_empty(head) && (head->next == head->prev); -} - -static inline void __list_cut_position(struct list_head *list, - struct list_head *head, struct list_head *entry) -{ - struct list_head *new_first = entry->next; - list->next = head->next; - list->next->prev = list; - list->prev = entry; - entry->next = list; - head->next = new_first; - new_first->prev = head; -} - -/** - * list_cut_position - cut a list into two - * @list: a new list to add all removed entries - * @head: a list with entries - * @entry: an entry within head, could be the head itself - * and if so we won't cut the list - * - * This helper moves the initial part of @head, up to and - * including @entry, from @head to @list. You should - * pass on @entry an element you know is on @head. @list - * should be an empty list or a list you do not care about - * losing its data. - * - */ -static inline void list_cut_position(struct list_head *list, - struct list_head *head, struct list_head *entry) -{ - if (list_empty(head)) - return; - if (list_is_singular(head) && - (head->next != entry && head != entry)) - return; - if (entry == head) - INIT_LIST_HEAD(list); - else - __list_cut_position(list, head, entry); -} - -static inline void __list_splice(const struct list_head *list, - struct list_head *prev, - struct list_head *next) -{ - struct list_head *first = list->next; - struct list_head *last = list->prev; - - first->prev = prev; - prev->next = first; - - last->next = next; - next->prev = last; -} - -/** - * list_splice - join two lists, this is designed for stacks - * @list: the new list to add. - * @head: the place to add it in the first list. - */ -static inline void list_splice(const struct list_head *list, - struct list_head *head) -{ - if (!list_empty(list)) - __list_splice(list, head, head->next); -} - -/** - * list_splice_tail - join two lists, each list being a queue - * @list: the new list to add. - * @head: the place to add it in the first list. - */ -static inline void list_splice_tail(struct list_head *list, - struct list_head *head) -{ - if (!list_empty(list)) - __list_splice(list, head->prev, head); -} - -/** - * list_splice_init - join two lists and reinitialise the emptied list. - * @list: the new list to add. - * @head: the place to add it in the first list. - * - * The list at @list is reinitialised - */ -static inline void list_splice_init(struct list_head *list, - struct list_head *head) -{ - if (!list_empty(list)) { - __list_splice(list, head, head->next); - INIT_LIST_HEAD(list); - } -} - -/** - * list_splice_tail_init - join two lists and reinitialise the emptied list - * @list: the new list to add. - * @head: the place to add it in the first list. - * - * Each of the lists is a queue. - * The list at @list is reinitialised - */ -static inline void list_splice_tail_init(struct list_head *list, - struct list_head *head) -{ - if (!list_empty(list)) { - __list_splice(list, head->prev, head); - INIT_LIST_HEAD(list); - } -} - -/** - * list_entry - get the struct for this entry - * @ptr: the &struct list_head pointer. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_struct within the struct. - */ -#define list_entry(ptr, type, member) \ - container_of(ptr, type, member) - -/** - * list_first_entry - get the first element from a list - * @ptr: the list head to take the element from. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_struct within the struct. - * - * Note, that list is expected to be not empty. - */ -#define list_first_entry(ptr, type, member) \ - list_entry((ptr)->next, type, member) - -/** - * list_for_each - iterate over a list - * @pos: the &struct list_head to use as a loop cursor. - * @head: the head for your list. - */ -#define list_for_each(pos, head) \ - for (pos = (head)->next; prefetch(pos->next), pos != (head); \ - pos = pos->next) - -/** - * __list_for_each - iterate over a list - * @pos: the &struct list_head to use as a loop cursor. - * @head: the head for your list. - * - * This variant differs from list_for_each() in that it's the - * simplest possible list iteration code, no prefetching is done. - * Use this for code that knows the list to be very short (empty - * or 1 entry) most of the time. - */ -#define __list_for_each(pos, head) \ - for (pos = (head)->next; pos != (head); pos = pos->next) - -/** - * list_for_each_prev - iterate over a list backwards - * @pos: the &struct list_head to use as a loop cursor. - * @head: the head for your list. - */ -#define list_for_each_prev(pos, head) \ - for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \ - pos = pos->prev) - -/** - * list_for_each_safe - iterate over a list safe against removal of list entry - * @pos: the &struct list_head to use as a loop cursor. - * @n: another &struct list_head to use as temporary storage - * @head: the head for your list. - */ -#define list_for_each_safe(pos, n, head) \ - for (pos = (head)->next, n = pos->next; pos != (head); \ - pos = n, n = pos->next) - -/** - * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry - * @pos: the &struct list_head to use as a loop cursor. - * @n: another &struct list_head to use as temporary storage - * @head: the head for your list. - */ -#define list_for_each_prev_safe(pos, n, head) \ - for (pos = (head)->prev, n = pos->prev; \ - prefetch(pos->prev), pos != (head); \ - pos = n, n = pos->prev) - -/** - * list_for_each_entry - iterate over list of given type - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry(pos, head, member) \ - for (pos = list_entry((head)->next, typeof(*pos), member); \ - prefetch(pos->member.next), &pos->member != (head); \ - pos = list_entry(pos->member.next, typeof(*pos), member)) - -/** - * list_for_each_entry_reverse - iterate backwards over list of given type. - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry_reverse(pos, head, member) \ - for (pos = list_entry((head)->prev, typeof(*pos), member); \ - prefetch(pos->member.prev), &pos->member != (head); \ - pos = list_entry(pos->member.prev, typeof(*pos), member)) - -/** - * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue() - * @pos: the type * to use as a start point - * @head: the head of the list - * @member: the name of the list_struct within the struct. - * - * Prepares a pos entry for use as a start point in list_for_each_entry_continue(). - */ -#define list_prepare_entry(pos, head, member) \ - ((pos) ? : list_entry(head, typeof(*pos), member)) - -/** - * list_for_each_entry_continue - continue iteration over list of given type - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Continue to iterate over list of given type, continuing after - * the current position. - */ -#define list_for_each_entry_continue(pos, head, member) \ - for (pos = list_entry(pos->member.next, typeof(*pos), member); \ - prefetch(pos->member.next), &pos->member != (head); \ - pos = list_entry(pos->member.next, typeof(*pos), member)) - -/** - * list_for_each_entry_continue_reverse - iterate backwards from the given point - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Start to iterate over list of given type backwards, continuing after - * the current position. - */ -#define list_for_each_entry_continue_reverse(pos, head, member) \ - for (pos = list_entry(pos->member.prev, typeof(*pos), member); \ - prefetch(pos->member.prev), &pos->member != (head); \ - pos = list_entry(pos->member.prev, typeof(*pos), member)) - -/** - * list_for_each_entry_from - iterate over list of given type from the current point - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Iterate over list of given type, continuing from current position. - */ -#define list_for_each_entry_from(pos, head, member) \ - for (; prefetch(pos->member.next), &pos->member != (head); \ - pos = list_entry(pos->member.next, typeof(*pos), member)) - -/** - * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry - * @pos: the type * to use as a loop cursor. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry_safe(pos, n, head, member) \ - for (pos = list_entry((head)->next, typeof(*pos), member), \ - n = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, typeof(*n), member)) - -/** - * list_for_each_entry_safe_continue - * @pos: the type * to use as a loop cursor. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Iterate over list of given type, continuing after current point, - * safe against removal of list entry. - */ -#define list_for_each_entry_safe_continue(pos, n, head, member) \ - for (pos = list_entry(pos->member.next, typeof(*pos), member), \ - n = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, typeof(*n), member)) - -/** - * list_for_each_entry_safe_from - * @pos: the type * to use as a loop cursor. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Iterate over list of given type from current point, safe against - * removal of list entry. - */ -#define list_for_each_entry_safe_from(pos, n, head, member) \ - for (n = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, typeof(*n), member)) - -/** - * list_for_each_entry_safe_reverse - * @pos: the type * to use as a loop cursor. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Iterate backwards over list of given type, safe against removal - * of list entry. - */ -#define list_for_each_entry_safe_reverse(pos, n, head, member) \ - for (pos = list_entry((head)->prev, typeof(*pos), member), \ - n = list_entry(pos->member.prev, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.prev, typeof(*n), member)) - -/* - * Double linked lists with a single pointer list head. - * Mostly useful for hash tables where the two pointer list head is - * too wasteful. - * You lose the ability to access the tail in O(1). - */ - -struct hlist_head { - struct hlist_node *first; -}; - -struct hlist_node { - struct hlist_node *next, **pprev; -}; - -#define HLIST_HEAD_INIT { .first = NULL } -#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } -#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) -static inline void INIT_HLIST_NODE(struct hlist_node *h) -{ - h->next = NULL; - h->pprev = NULL; -} - -static inline int hlist_unhashed(const struct hlist_node *h) -{ - return !h->pprev; -} - -static inline int hlist_empty(const struct hlist_head *h) -{ - return !h->first; -} - -static inline void __hlist_del(struct hlist_node *n) -{ - struct hlist_node *next = n->next; - struct hlist_node **pprev = n->pprev; - *pprev = next; - if (next) - next->pprev = pprev; -} - -static inline void hlist_del(struct hlist_node *n) -{ - __hlist_del(n); - n->next = LIST_POISON1; - n->pprev = LIST_POISON2; -} - -static inline void hlist_del_init(struct hlist_node *n) -{ - if (!hlist_unhashed(n)) { - __hlist_del(n); - INIT_HLIST_NODE(n); - } -} - -static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) -{ - struct hlist_node *first = h->first; - n->next = first; - if (first) - first->pprev = &n->next; - h->first = n; - n->pprev = &h->first; -} - -/* next must be != NULL */ -static inline void hlist_add_before(struct hlist_node *n, - struct hlist_node *next) -{ - n->pprev = next->pprev; - n->next = next; - next->pprev = &n->next; - *(n->pprev) = n; -} - -static inline void hlist_add_after(struct hlist_node *n, - struct hlist_node *next) -{ - next->next = n->next; - n->next = next; - next->pprev = &n->next; - - if(next->next) - next->next->pprev = &next->next; -} - -/* - * Move a list from one list head to another. Fixup the pprev - * reference of the first entry if it exists. - */ -static inline void hlist_move_list(struct hlist_head *old, - struct hlist_head *new) -{ - new->first = old->first; - if (new->first) - new->first->pprev = &new->first; - old->first = NULL; -} - -#define hlist_entry(ptr, type, member) container_of(ptr,type,member) - -#define hlist_for_each(pos, head) \ - for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \ - pos = pos->next) - -#define hlist_for_each_safe(pos, n, head) \ - for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \ - pos = n) - -/** - * hlist_for_each_entry - iterate over list of given type - * @tpos: the type * to use as a loop cursor. - * @pos: the &struct hlist_node to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry(tpos, pos, head, member) \ - for (pos = (head)->first; \ - pos && ({ prefetch(pos->next); 1;}) && \ - ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ - pos = pos->next) - -/** - * hlist_for_each_entry_continue - iterate over a hlist continuing after current point - * @tpos: the type * to use as a loop cursor. - * @pos: the &struct hlist_node to use as a loop cursor. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry_continue(tpos, pos, member) \ - for (pos = (pos)->next; \ - pos && ({ prefetch(pos->next); 1;}) && \ - ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ - pos = pos->next) - -/** - * hlist_for_each_entry_from - iterate over a hlist continuing from current point - * @tpos: the type * to use as a loop cursor. - * @pos: the &struct hlist_node to use as a loop cursor. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry_from(tpos, pos, member) \ - for (; pos && ({ prefetch(pos->next); 1;}) && \ - ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ - pos = pos->next) - -/** - * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry - * @tpos: the type * to use as a loop cursor. - * @pos: the &struct hlist_node to use as a loop cursor. - * @n: another &struct hlist_node to use as temporary storage - * @head: the head for your list. - * @member: the name of the hlist_node within the struct. - */ -#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \ - for (pos = (head)->first; \ - pos && ({ n = pos->next; 1; }) && \ - ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ - pos = n) - -#endif -- 2.34.1 From 5e13fab888d07ba3657ac9e1eb0441450ea17837 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 10 May 2009 22:24:24 -0400 Subject: [PATCH 10/16] Add final license to test file, cleanup makefile Signed-off-by: Mathieu Desnoyers --- LICENSE | 1 + Makefile | 2 +- urcu-asm.c | 22 ++++++++++++++++++++++ 3 files changed, 24 insertions(+), 1 deletion(-) diff --git a/LICENSE b/LICENSE index f2b5228..6a52b4b 100644 --- a/LICENSE +++ b/LICENSE @@ -30,3 +30,4 @@ api_ppc.h test_urcu.c test_urcu_yield.c test_rwlock_timing.c +urcu-asm.c diff --git a/Makefile b/Makefile index 093bf66..1965a77 100644 --- a/Makefile +++ b/Makefile @@ -68,4 +68,4 @@ install: liburcu.so clean: rm -f *.o test_urcu test_urcu_timing test_rwlock_timing urcu-asm.S \ test_urcu_yield urcutorture urcutorture-yield liburcu.so \ - test_urcu_dynamic_link + test_urcu_dynamic_link api.h arch.h diff --git a/urcu-asm.c b/urcu-asm.c index 19a5b0c..0e833f4 100644 --- a/urcu-asm.c +++ b/urcu-asm.c @@ -1,3 +1,25 @@ +/* + * urcu-asm.c + * + * Userspace RCU library - assembly dump of primitives + * + * Copyright February 2009 - Mathieu Desnoyers + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + #include "urcu.h" void show_read_lock(void) -- 2.34.1 From d2d2303563e2b260114bc0aa679d8c256eb0a43e Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 10 May 2009 22:50:48 -0400 Subject: [PATCH 11/16] Fix precompiler error in arch_*.h, add arch-api test Signed-off-by: Mathieu Desnoyers --- Makefile | 9 +++++++-- arch_ppc.h | 2 +- arch_x86.h | 2 +- urcu-static.h | 23 ++++++++++++++++++----- 4 files changed, 27 insertions(+), 9 deletions(-) diff --git a/Makefile b/Makefile index 1965a77..20024c6 100644 --- a/Makefile +++ b/Makefile @@ -11,10 +11,15 @@ LDFLAGS=-lpthread SRC_DEP=`echo $^ | sed 's/[^ ]*.h//g'` -all: test_urcu test_urcu_dynamic_link test_urcu_timing \ +all: arch-api test_urcu test_urcu_dynamic_link test_urcu_timing \ test_rwlock_timing test_urcu_yield urcu-asm.S \ urcu-asm.o urcutorture urcutorture-yield liburcu.so +arch-api: api.h arch.h + # Run either make pthreads-x86 or make pthreads-ppc prior to build + # the RCU library. Architecture auto-detectection not implemented + # in the build system yet. + pthreads-x86: clean cp api_x86.h api.h cp arch_x86.h arch.h @@ -59,7 +64,7 @@ urcutorture: urcutorture.c urcu.o urcu.h rcutorture.h urcutorture-yield: urcutorture.c urcu-yield.o urcu.h rcutorture.h $(CC) -DDEBUG_YIELD ${CFLAGS} $(LDFLAGS) -o $@ $(SRC_DEP) -.PHONY: clean install +.PHONY: clean install arch-api install: liburcu.so cp -f liburcu.so /usr/lib/ diff --git a/arch_ppc.h b/arch_ppc.h index 1a34024..40d186b 100644 --- a/arch_ppc.h +++ b/arch_ppc.h @@ -28,7 +28,7 @@ #define CONFIG_HAVE_MEM_COHERENCY #ifndef BITS_PER_LONG -#define BITS_PER_LONG (sizeof(unsigned long) * 8) +#define BITS_PER_LONG (sizeof(unsigned long) * 8) #endif #define mb() asm volatile("sync":::"memory") diff --git a/arch_x86.h b/arch_x86.h index 01b5d50..e899684 100644 --- a/arch_x86.h +++ b/arch_x86.h @@ -29,7 +29,7 @@ #define CONFIG_HAVE_MEM_COHERENCY #ifndef BITS_PER_LONG -#define BITS_PER_LONG (sizeof(unsigned long) * 8) +#define BITS_PER_LONG (__SIZEOF_LONG__ * 8) #endif #ifdef CONFIG_HAVE_FENCE diff --git a/urcu-static.h b/urcu-static.h index c47a759..f1aab2f 100644 --- a/urcu-static.h +++ b/urcu-static.h @@ -4,14 +4,27 @@ /* * urcu-static.h * - * Userspace RCU header, to be included only in LGPL-compatible code. + * Userspace RCU header. * - * Copyright February 2009 - Mathieu Desnoyers + * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See urcu.h for linking + * dynamically with the userspace rcu library. * - * Credits for Paul E. McKenney - * for inspiration coming from the Linux kernel RCU and rcu-preempt. + * Copyright (c) 2009 Mathieu Desnoyers + * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. * - * Distributed under LGPLv2.1 + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * * IBM's contributions to this file may be relicensed under LGPLv2 or later. */ -- 2.34.1 From 41e6b690646e062c78616bf9900a883e7ecced59 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 10 May 2009 22:53:36 -0400 Subject: [PATCH 12/16] Fix arch_ppc precompiler error Signed-off-by: Mathieu Desnoyers --- arch_ppc.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/arch_ppc.h b/arch_ppc.h index 40d186b..794c9fc 100644 --- a/arch_ppc.h +++ b/arch_ppc.h @@ -28,7 +28,7 @@ #define CONFIG_HAVE_MEM_COHERENCY #ifndef BITS_PER_LONG -#define BITS_PER_LONG (sizeof(unsigned long) * 8) +#define BITS_PER_LONG (__SIZEOF_LONG__ * 8) #endif #define mb() asm volatile("sync":::"memory") -- 2.34.1 From 3162dfe1928d4d6bf857f8e9e1c814eb8a994a0d Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 11 May 2009 16:58:17 -0400 Subject: [PATCH 13/16] Add Paul's URCU model Signed-off-by: Mathieu Desnoyers --- formal-model/urcu-paulmck/urcu-paulmck.spin | 299 ++++++++++++++++++++ formal-model/urcu-paulmck/urcu.sh | 3 + 2 files changed, 302 insertions(+) create mode 100644 formal-model/urcu-paulmck/urcu-paulmck.spin create mode 100644 formal-model/urcu-paulmck/urcu.sh diff --git a/formal-model/urcu-paulmck/urcu-paulmck.spin b/formal-model/urcu-paulmck/urcu-paulmck.spin new file mode 100644 index 0000000..e20a6e5 --- /dev/null +++ b/formal-model/urcu-paulmck/urcu-paulmck.spin @@ -0,0 +1,299 @@ +/* + * urcu_mbmin.spin: Promela code to validate urcu. See commit number + * 3a9e6e9df706b8d39af94d2f027210e2e7d4106e of Mathieu Desnoyer's + * git archive at git://lttng.org/userspace-rcu.git, but with + * memory barriers removed. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * Copyright (c) 2009 Paul E. McKenney, IBM Corporation. + */ + +/* Promela validation variables. */ + +bit removed = 0; /* Has RCU removal happened, e.g., list_del_rcu()? */ +bit free = 0; /* Has RCU reclamation happened, e.g., kfree()? */ +bit need_mb = 0; /* =1 says need reader mb, =0 for reader response. */ +byte reader_progress[4]; + /* Count of read-side statement executions. */ + +/* urcu definitions and variables, taken straight from the algorithm. */ + +#define RCU_GP_CTR_BIT (1 << 7) +#define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BIT - 1) + +byte urcu_gp_ctr = 1; +byte urcu_active_readers = 0; + +/* Model the RCU read-side critical section. */ + +proctype urcu_reader() +{ + bit done = 0; + bit mbok; + byte tmp; + byte tmp_removed; + byte tmp_free; + + /* Absorb any early requests for memory barriers. */ + do + :: need_mb == 1 -> + need_mb = 0; + :: 1 -> skip; + :: 1 -> break; + od; + + /* + * Each pass through this loop executes one read-side statement + * from the following code fragment: + * + * rcu_read_lock(); [0a] + * rcu_read_lock(); [0b] + * p = rcu_dereference(global_p); [1] + * x = p->data; [2] + * rcu_read_unlock(); [3b] + * rcu_read_unlock(); [3a] + * + * Because we are modeling a weak-memory machine, these statements + * can be seen in any order, the only restriction being that + * rcu_read_unlock() cannot precede the corresponding rcu_read_lock(). + * The placement of the inner rcu_read_lock() and rcu_read_unlock() + * is non-deterministic, the above is but one possible placement. + * Intestingly enough, this model validates all possible placements + * of the inner rcu_read_lock() and rcu_read_unlock() statements, + * with the only constraint being that the rcu_read_lock() must + * precede the rcu_read_unlock(). + * + * We also respond to memory-barrier requests, but only if our + * execution happens to be ordered. If the current state is + * misordered, we ignore memory-barrier requests. + */ + do + :: 1 -> + if + :: reader_progress[0] < 2 -> /* [0a and 0b] */ + tmp = urcu_active_readers; + if + :: (tmp & RCU_GP_CTR_NEST_MASK) == 0 -> + tmp = urcu_gp_ctr; + do + :: (reader_progress[1] + + reader_progress[2] + + reader_progress[3] == 0) && need_mb == 1 -> + need_mb = 0; + :: 1 -> skip; + :: 1 -> break; + od; + urcu_active_readers = tmp; + :: else -> + urcu_active_readers = tmp + 1; + fi; + reader_progress[0] = reader_progress[0] + 1; + :: reader_progress[1] == 0 -> /* [1] */ + tmp_removed = removed; + reader_progress[1] = 1; + :: reader_progress[2] == 0 -> /* [2] */ + tmp_free = free; + reader_progress[2] = 1; + :: ((reader_progress[0] > reader_progress[3]) && + (reader_progress[3] < 2)) -> /* [3a and 3b] */ + tmp = urcu_active_readers - 1; + urcu_active_readers = tmp; + reader_progress[3] = reader_progress[3] + 1; + :: else -> break; + fi; + + /* Process memory-barrier requests, if it is safe to do so. */ + atomic { + mbok = 0; + tmp = 0; + do + :: tmp < 4 && reader_progress[tmp] == 0 -> + tmp = tmp + 1; + break; + :: tmp < 4 && reader_progress[tmp] != 0 -> + tmp = tmp + 1; + :: tmp >= 4 && + reader_progress[0] == reader_progress[3] -> + done = 1; + break; + :: tmp >= 4 && + reader_progress[0] != reader_progress[3] -> + break; + od; + do + :: tmp < 4 && reader_progress[tmp] == 0 -> + tmp = tmp + 1; + :: tmp < 4 && reader_progress[tmp] != 0 -> + break; + :: tmp >= 4 -> + mbok = 1; + break; + od + + } + + if + :: mbok == 1 -> + /* We get here if mb processing is safe. */ + do + :: need_mb == 1 -> + need_mb = 0; + :: 1 -> skip; + :: 1 -> break; + od; + :: else -> skip; + fi; + + /* + * Check to see if we have modeled the entire RCU read-side + * critical section, and leave if so. + */ + if + :: done == 1 -> break; + :: else -> skip; + fi + od; + assert((tmp_free == 0) || (tmp_removed == 1)); + + /* Process any late-arriving memory-barrier requests. */ + do + :: need_mb == 1 -> + need_mb = 0; + :: 1 -> skip; + :: 1 -> break; + od; +} + +/* Model the RCU update process. */ + +proctype urcu_updater() +{ + byte tmp; + + /* prior synchronize_rcu(), second counter flip. */ + need_mb = 1; /* mb() A */ + do + :: need_mb == 1 -> skip; + :: need_mb == 0 -> break; + od; + urcu_gp_ctr = urcu_gp_ctr + RCU_GP_CTR_BIT; + need_mb = 1; /* mb() B */ + do + :: need_mb == 1 -> skip; + :: need_mb == 0 -> break; + od; + do + :: 1 -> + if + :: (urcu_active_readers & RCU_GP_CTR_NEST_MASK) != 0 && + (urcu_active_readers & ~RCU_GP_CTR_NEST_MASK) != + (urcu_gp_ctr & ~RCU_GP_CTR_NEST_MASK) -> + skip; + :: else -> break; + fi + od; + need_mb = 1; /* mb() C absolutely required by analogy with G */ + do + :: need_mb == 1 -> skip; + :: need_mb == 0 -> break; + od; + + /* Removal statement, e.g., list_del_rcu(). */ + removed = 1; + + /* current synchronize_rcu(), first counter flip. */ + need_mb = 1; /* mb() D suggested */ + do + :: need_mb == 1 -> skip; + :: need_mb == 0 -> break; + od; + urcu_gp_ctr = urcu_gp_ctr + RCU_GP_CTR_BIT; + need_mb = 1; /* mb() E required if D not present */ + do + :: need_mb == 1 -> skip; + :: need_mb == 0 -> break; + od; + + /* current synchronize_rcu(), first-flip check plus second flip. */ + if + :: 1 -> + do + :: 1 -> + if + :: (urcu_active_readers & RCU_GP_CTR_NEST_MASK) != 0 && + (urcu_active_readers & ~RCU_GP_CTR_NEST_MASK) != + (urcu_gp_ctr & ~RCU_GP_CTR_NEST_MASK) -> + skip; + :: else -> break; + fi; + od; + urcu_gp_ctr = urcu_gp_ctr + RCU_GP_CTR_BIT; + :: 1 -> + tmp = urcu_gp_ctr; + urcu_gp_ctr = urcu_gp_ctr + RCU_GP_CTR_BIT; + do + :: 1 -> + if + :: (urcu_active_readers & RCU_GP_CTR_NEST_MASK) != 0 && + (urcu_active_readers & ~RCU_GP_CTR_NEST_MASK) != + (tmp & ~RCU_GP_CTR_NEST_MASK) -> + skip; + :: else -> break; + fi; + od; + fi; + + /* current synchronize_rcu(), second counter flip check. */ + need_mb = 1; /* mb() F not required */ + do + :: need_mb == 1 -> skip; + :: need_mb == 0 -> break; + od; + do + :: 1 -> + if + :: (urcu_active_readers & RCU_GP_CTR_NEST_MASK) != 0 && + (urcu_active_readers & ~RCU_GP_CTR_NEST_MASK) != + (urcu_gp_ctr & ~RCU_GP_CTR_NEST_MASK) -> + skip; + :: else -> break; + fi; + od; + need_mb = 1; /* mb() G absolutely required */ + do + :: need_mb == 1 -> skip; + :: need_mb == 0 -> break; + od; + + /* free-up step, e.g., kfree(). */ + free = 1; +} + +/* + * Initialize the array, spawn a reader and an updater. Because readers + * are independent of each other, only one reader is needed. + */ + +init { + atomic { + reader_progress[0] = 0; + reader_progress[1] = 0; + reader_progress[2] = 0; + reader_progress[3] = 0; + run urcu_reader(); + run urcu_updater(); + } +} diff --git a/formal-model/urcu-paulmck/urcu.sh b/formal-model/urcu-paulmck/urcu.sh new file mode 100644 index 0000000..8ef0e87 --- /dev/null +++ b/formal-model/urcu-paulmck/urcu.sh @@ -0,0 +1,3 @@ +spin -a urcu-paulmck.spin +cc -DSAFETY -o pan pan.c +./pan -- 2.34.1 From 0114ba7f23f86623c237baeb28ec8e4b39b9bb84 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 12 May 2009 15:28:55 -0400 Subject: [PATCH 14/16] Implementation of xchg primitives derived from MIT license See LICENSE for details. Signed-off-by: Mathieu Desnoyers --- LICENSE | 27 +++++++++++++ Makefile | 6 ++- arch_atomic_ppc.h | 99 +++++++++++++++++++++++++++++++++++++++++++++++ arch_atomic_x86.h | 92 +++++++++++++++++++++++++++++++++++++++++++ arch_ppc.h | 79 +------------------------------------ arch_x86.h | 51 +----------------------- 6 files changed, 224 insertions(+), 130 deletions(-) create mode 100644 arch_atomic_ppc.h create mode 100644 arch_atomic_x86.h diff --git a/LICENSE b/LICENSE index 6a52b4b..4aba776 100644 --- a/LICENSE +++ b/LICENSE @@ -2,6 +2,9 @@ Userspace RCU library licensing Mathieu Desnoyers May 10, 2009 + +* LGPLv2.1 + The library part is distributed under LGPLv2.1 or later. See lgpl-2.1.txt for details. This applies to : @@ -20,6 +23,23 @@ Dynamic-only linking with the LGPL library is used if _LGPL_SOURCE is not defined. It permits relinking with newer versions of the library, which is required by the LGPL license. + +* MIT-style license : + +xchg() privimitive has been rewritten from scratch starting from atomic_ops 1.2 +which has a MIT-style license that is intended to allow use in both free and +proprietary software: + http://www.hpl.hp.com/research/linux/atomic_ops/LICENSING.txt + http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_source/ + +This license applies to : + +arch_atomic_x86.h +arch_atomic_ppc.h + + +* GPLv2 + Library test code is distributed under the GPLv2 license. See gpl-2.0.txt for details. This applies to : @@ -31,3 +51,10 @@ test_urcu.c test_urcu_yield.c test_rwlock_timing.c urcu-asm.c + + +Various details : + +ACCESS_ONCE(), likely(), unlikely() and barrier() are considered trivial enough +that copyright does not apply to them. I (Mathieu Desnoyers) re-typed them from +scratch in a mail client just to prove it. diff --git a/Makefile b/Makefile index 20024c6..079a9e3 100644 --- a/Makefile +++ b/Makefile @@ -23,10 +23,12 @@ arch-api: api.h arch.h pthreads-x86: clean cp api_x86.h api.h cp arch_x86.h arch.h + cp arch_atomic_x86.h arch_atomic.h pthreads-ppc: clean cp api_ppc.h api.h cp arch_ppc.h arch.h + cp arch_atomic_ppc.h arch_atomic.h test_urcu: urcu.o test_urcu.c urcu.h $(CC) ${CFLAGS} $(LDFLAGS) -o $@ $(SRC_DEP) @@ -68,9 +70,9 @@ urcutorture-yield: urcutorture.c urcu-yield.o urcu.h rcutorture.h install: liburcu.so cp -f liburcu.so /usr/lib/ - cp -f arch.h compiler.h urcu.h urcu-static.h /usr/include/ + cp -f arch.h arch_atomic.h compiler.h urcu.h urcu-static.h /usr/include/ clean: rm -f *.o test_urcu test_urcu_timing test_rwlock_timing urcu-asm.S \ test_urcu_yield urcutorture urcutorture-yield liburcu.so \ - test_urcu_dynamic_link api.h arch.h + test_urcu_dynamic_link api.h arch.h arch_atomic.h diff --git a/arch_atomic_ppc.h b/arch_atomic_ppc.h new file mode 100644 index 0000000..13d56b4 --- /dev/null +++ b/arch_atomic_ppc.h @@ -0,0 +1,99 @@ +#ifndef _ARCH_ATOMIC_PPC_H +#define _ARCH_ATOMIC_PPC_H + +/* + * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved. + * Copyright (c) 1996-1999 by Silicon Graphics. All rights reserved. + * Copyright (c) 1999-2004 Hewlett-Packard Development Company, L.P. + * Copyright (c) 2009 Mathieu Desnoyers + * + * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED + * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. + * + * Permission is hereby granted to use or copy this program + * for any purpose, provided the above notices are retained on all copies. + * Permission to modify the code and to distribute modified code is granted, + * provided the above notices are retained, and a notice that the code was + * modified is included with the above copyright notice. + * + * Code inspired from libatomic_ops-1.2, inherited in part from the + * Boehm-Demers-Weiser conservative garbage collector. + */ + +#ifndef BITS_PER_LONG +#define BITS_PER_LONG (__SIZEOF_LONG__ * 8) +#endif + +#define ILLEGAL_INSTR .long 0xd00d00 + +#ifndef _INCLUDE_API_H + +/* + * Using a isync as second barrier for exchange to provide acquire semantic. + * According to atomic_ops/sysdeps/gcc/powerpc.h, the documentation is "fairly + * explicit that this also has acquire semantics." + * Derived from AO_compare_and_swap(), but removed the comparison. + */ + +static __attribute__((always_inline)) +unsigned int atomic_exchange_32(volatile unsigned int *addr, unsigned int val) +{ + unsigned int result; + + __asm__ __volatile__( + "lwsync\n" + "1:\t" "lwarx %0,0,%1\n" /* load and reserve */ + "stwcx. %2,0,%1\n" /* else store conditional */ + "bne- 1b\n" /* retry if lost reservation */ + "isync\n" + : "=&r"(result), + : "r"(addr), "r"(val) + : "memory", "cc"); + + return result; +} + +#if (BITS_PER_LONG == 64) + +static __attribute__((always_inline)) +unsigned long atomic_exchange_64(volatile unsigned long *addr, + unsigned long val) +{ + unsigned long result; + + __asm__ __volatile__( + "lwsync\n" + "1:\t" "ldarx %0,0,%1\n" /* load and reserve */ + "stdcx. %2,0,%1\n" /* else store conditional */ + "bne- 1b\n" /* retry if lost reservation */ + "isync\n" + : "=&r"(result), + : "r"(addr), "r"(val) + : "memory", "cc"); + + return result; +} + +#endif + +static __attribute__((always_inline)) +unsigned long _atomic_exchange(volatile void *addr, unsigned long val, int len) +{ + switch (len) { + case 4: return atomic_exchange_32(addr, val); +#if (BITS_PER_LONG == 64) + case 8: return atomic_exchange_64(addr, val); +#endif + } + /* generate an illegal instruction. Cannot catch this with linker tricks + * when optimizations are disabled. */ + __asm__ __volatile__(ILLEGAL_INSTR); + return 0; +} + +#define xchg(addr, v) (__typeof__(*(addr)) _atomic_exchange((addr), (v), \ + sizeof(*(addr)))) + +#endif /* #ifndef _INCLUDE_API_H */ + +#endif /* ARCH_ATOMIC_PPC_H */ diff --git a/arch_atomic_x86.h b/arch_atomic_x86.h new file mode 100644 index 0000000..e9a0b3e --- /dev/null +++ b/arch_atomic_x86.h @@ -0,0 +1,92 @@ +#ifndef _ARCH_ATOMIC_X86_H +#define _ARCH_ATOMIC_X86_H + +/* + * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved. + * Copyright (c) 1996-1999 by Silicon Graphics. All rights reserved. + * Copyright (c) 1999-2004 Hewlett-Packard Development Company, L.P. + * Copyright (c) 2009 Mathieu Desnoyers + * + * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED + * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. + * + * Permission is hereby granted to use or copy this program + * for any purpose, provided the above notices are retained on all copies. + * Permission to modify the code and to distribute modified code is granted, + * provided the above notices are retained, and a notice that the code was + * modified is included with the above copyright notice. + * + * Code inspired from libatomic_ops-1.2, inherited in part from the + * Boehm-Demers-Weiser conservative garbage collector. + */ + +#ifndef BITS_PER_LONG +#define BITS_PER_LONG (__SIZEOF_LONG__ * 8) +#endif + +#ifndef _INCLUDE_API_H + +/* + * Using a isync as second barrier for exchange to provide acquire semantic. + * According to atomic_ops/sysdeps/gcc/powerpc.h, the documentation is "fairly + * explicit that this also has acquire semantics." + * Derived from AO_compare_and_swap() and AO_test_and_set_full(). + */ + +static __attribute__((always_inline)) +unsigned int atomic_exchange_32(volatile unsigned int *addr, unsigned int val) +{ + unsigned int result; + + __asm__ __volatile__( + /* Note: the "xchg" instruction does not need a "lock" prefix */ + "xchgl %0, %1" + : "=&r"(result), "=m"(*addr) + : "0" (val), "m"(*addr) + : "memory"); + + return result; +} + +#if (BITS_PER_LONG == 64) + +static __attribute__((always_inline)) +unsigned long atomic_exchange_64(volatile unsigned long *addr, + unsigned long val) +{ + unsigned long result; + + __asm__ __volatile__( + /* Note: the "xchg" instruction does not need a "lock" prefix */ + "xchgq %0, %1" + : "=&r"(result), "=m"(*addr) + : "0" (val), "m"(*addr) + : "memory"); + + return result; +} + +#endif + +static __attribute__((always_inline)) +unsigned long _atomic_exchange(volatile void *addr, unsigned long val, int len) +{ + switch (len) { + case 4: return atomic_exchange_32(addr, val); +#if (BITS_PER_LONG == 64) + case 8: return atomic_exchange_64(addr, val); +#endif + } + /* generate an illegal instruction. Cannot catch this with linker tricks + * when optimizations are disabled. */ + __asm__ __volatile__("ud2"); + return 0; +} + +#define xchg(addr, v) \ + ((__typeof__(*(addr))) _atomic_exchange((addr), (unsigned long)(v), \ + sizeof(*(addr)))) + +#endif /* #ifndef _INCLUDE_API_H */ + +#endif /* ARCH_ATOMIC_X86_H */ diff --git a/arch_ppc.h b/arch_ppc.h index 794c9fc..c68790f 100644 --- a/arch_ppc.h +++ b/arch_ppc.h @@ -23,6 +23,7 @@ */ #include +#include #define CONFIG_HAVE_FENCE 1 #define CONFIG_HAVE_MEM_COHERENCY @@ -77,84 +78,6 @@ static inline void cpu_relax(void) barrier(); } -#define PPC405_ERR77(ra,rb) -#define LWSYNC_ON_SMP "\n\tlwsync\n" -#define ISYNC_ON_SMP "\n\tisync\n" - -struct __xchg_dummy { - unsigned long a[100]; -}; -#define __xg(x) ((struct __xchg_dummy *)(x)) - -#ifndef _INCLUDE_API_H - -/* - * Exchange the 32-bits value pointed to by p, returns the old value. - * Might not work with PPC405 (see err 77). - */ -static __always_inline -unsigned int __xchg_u32(volatile void *p, unsigned int val) -{ - unsigned int prev; - - __asm__ __volatile__(LWSYNC_ON_SMP - "1:\t" "lwarx %0,0,%2\n" - "stwcx. %3,0,%2\n" - "bne- 1b" - ISYNC_ON_SMP - : "=&r" (prev), "+m" (*(volatile unsigned int *)p) - : "r" (p), "r" (val) - : "cc", "memory"); - return prev; -} - -#if (BITS_PER_LONG == 64) -/* - * Exchange the 64-bits value pointed to by p, returns the old value. - * Might not work with PPC405 (see err 77). - */ -static __always_inline -unsigned long __xchg_u64(volatile void *p, unsigned long val) -{ - unsigned long prev; - - __asm__ __volatile__(LWSYNC_ON_SMP - "1:\t" "ldarx %0,0,%2\n" - "stdcx. %3,0,%2\n" - "bne- 1b" - ISYNC_ON_SMP - : "=&r" (prev), "+m" (*(volatile unsigned long *)p) - : "r" (p), "r" (val) - : "cc", "memory"); - return prev; -} -#endif - -static __always_inline -unsigned long __xchg(volatile void *ptr, unsigned long x, int size) -{ - switch (size) { - case 4: - return __xchg_u32(ptr, x); -#if (BITS_PER_LONG == 64) - case 8: - return __xchg_u64(ptr, x); -#endif - } - return x; -} - -/* - * note : xchg should only be used with pointers to 32 or 64-bits elements. - * No build-time check is done on the element size because depending on - * non-referenced unexisting symbol at link time to provide an error message - * only work when compiling with optimizations. - */ -#define xchg(ptr, v) \ - ((__typeof__(*(ptr)))__xchg((ptr), (unsigned long)(v), sizeof(*(ptr)))) - -#endif /* #ifndef _INCLUDE_API_H */ - #define mftbl() \ ({ \ unsigned long rval; \ diff --git a/arch_x86.h b/arch_x86.h index e899684..cc3ab01 100644 --- a/arch_x86.h +++ b/arch_x86.h @@ -23,6 +23,7 @@ */ #include +#include /* Assume P4 or newer */ #define CONFIG_HAVE_FENCE 1 @@ -94,56 +95,6 @@ static inline void cpu_relax(void) rep_nop(); } -#define xchg(ptr, v) \ - ((__typeof__(*(ptr)))__xchg((ptr), (unsigned long)(v), sizeof(*(ptr)))) - -struct __xchg_ptr_as_array { - unsigned long a[100]; -}; - -#define __xchg_ptr_as_array(x) ((struct __xchg_ptr_as_array *)(x)) - -/* - * xchg always implies a "lock" prefix, even on UP. See Intel documentation. - * volatile attribute is neccessary due to xchg side effect. - * *ptr is an output argument. - * x is considered local, ptr is considered remote. - */ -static inline unsigned long __xchg(volatile void *ptr, unsigned long x, - int size) -{ - switch (size) { - case 1: - asm volatile("xchgb %b0,%1" - : "=q" (x) - : "m" (*__xchg_ptr_as_array(ptr)), "0" (x) - : "memory"); - break; - case 2: - asm volatile("xchgw %w0,%1" - : "=r" (x) - : "m" (*__xchg_ptr_as_array(ptr)), "0" (x) - : "memory"); - break; - case 4: - asm volatile("xchgl %k0,%1" - : "=r" (x) - : "m" (*__xchg_ptr_as_array(ptr)), "0" (x) - : "memory"); - break; -#if (BITS_PER_LONG == 64) - case 8: - asm volatile("xchgq %0,%1" - : "=r" (x) - : "m" (*__xchg_ptr_as_array(ptr)), "0" (x) - : "memory"); - break; -#endif - } - smp_wmc(); - return x; -} - #define rdtscll(val) \ do { \ unsigned int __a, __d; \ -- 2.34.1 From 33211b37023dac96a3e7a9fdf895c4810d14d585 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 12 May 2009 15:31:55 -0400 Subject: [PATCH 15/16] Remove bogus comment. Signed-off-by: Mathieu Desnoyers --- arch_atomic_x86.h | 3 --- 1 file changed, 3 deletions(-) diff --git a/arch_atomic_x86.h b/arch_atomic_x86.h index e9a0b3e..8423ae3 100644 --- a/arch_atomic_x86.h +++ b/arch_atomic_x86.h @@ -27,9 +27,6 @@ #ifndef _INCLUDE_API_H /* - * Using a isync as second barrier for exchange to provide acquire semantic. - * According to atomic_ops/sysdeps/gcc/powerpc.h, the documentation is "fairly - * explicit that this also has acquire semantics." * Derived from AO_compare_and_swap() and AO_test_and_set_full(). */ -- 2.34.1 From e7061ad2321fd7f553095c5c13319931d177494b Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Tue, 12 May 2009 23:43:01 -0400 Subject: [PATCH 16/16] Fix some typos in PowerPC support code. Signed-off-by: Paul E. McKenney Signed-off-by: Mathieu Desnoyers --- arch_atomic_ppc.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/arch_atomic_ppc.h b/arch_atomic_ppc.h index 13d56b4..587fb8b 100644 --- a/arch_atomic_ppc.h +++ b/arch_atomic_ppc.h @@ -24,7 +24,7 @@ #define BITS_PER_LONG (__SIZEOF_LONG__ * 8) #endif -#define ILLEGAL_INSTR .long 0xd00d00 +#define ILLEGAL_INSTR ".long 0xd00d00" #ifndef _INCLUDE_API_H @@ -46,7 +46,7 @@ unsigned int atomic_exchange_32(volatile unsigned int *addr, unsigned int val) "stwcx. %2,0,%1\n" /* else store conditional */ "bne- 1b\n" /* retry if lost reservation */ "isync\n" - : "=&r"(result), + : "=&r"(result) : "r"(addr), "r"(val) : "memory", "cc"); @@ -91,8 +91,8 @@ unsigned long _atomic_exchange(volatile void *addr, unsigned long val, int len) return 0; } -#define xchg(addr, v) (__typeof__(*(addr)) _atomic_exchange((addr), (v), \ - sizeof(*(addr)))) +#define xchg(addr, v) (__typeof__(*(addr))) _atomic_exchange((addr), (v), \ + sizeof(*(addr))) #endif /* #ifndef _INCLUDE_API_H */ -- 2.34.1