[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming.threads

A simple lock-free linked list source code?

Rick

7/20/2004 1:47:00 PM

Hi,

I am looking for any working source code for a simple lock-free linked list
that can be compiled and run on Linux and Intel.

Please reply with the URL or if as an attachment, to rickgoh(ADD)yahoo.com.

Example of such lock-free linked list is Timothy Harris's:
http://www.cl.cam.ac.uk/Research/SRG/netos/...

The website contains the publications and some code/library. However, there
isn't any lock-free linked list code. Only more complex ones like Skiplist,
binary search trees, etc.

Many thanks.


Regards,
Rick Goh
8 Answers

Joe Seigh

7/20/2004 2:42:00 PM

0



Rick wrote:
>
> Hi,
>
> I am looking for any working source code for a simple lock-free linked list
> that can be compiled and run on Linux and Intel.
>
> Please reply with the URL or if as an attachment, to rickgoh(ADD)yahoo.com.
>
> Example of such lock-free linked list is Timothy Harris's:
> http://www.cl.cam.ac.uk/Research/SRG/netos/...
>
> The website contains the publications and some code/library. However, there
> isn't any lock-free linked list code. Only more complex ones like Skiplist,
> binary search trees, etc.
>

What do you mean by linked list? There's algorithms for LIFO and FIFO queues.
If you want random insert and delete it's a bit more complex.

Joe Seigh

Rick

7/20/2004 3:36:00 PM

0

Hi,

I'm looking for random insert and delete.


"Joe Seigh" <jseigh_01@xemaps.com> wrote in message
news:40FD3136.A70D693@xemaps.com...
>
>
> Rick wrote:
> >
> > Hi,
> >
> > I am looking for any working source code for a simple lock-free linked
list
> > that can be compiled and run on Linux and Intel.
> >
> > Please reply with the URL or if as an attachment, to
rickgoh(ADD)yahoo.com.
> >
> > Example of such lock-free linked list is Timothy Harris's:
> > http://www.cl.cam.ac.uk/Research/SRG/netos/...
> >
> > The website contains the publications and some code/library. However,
there
> > isn't any lock-free linked list code. Only more complex ones like
Skiplist,
> > binary search trees, etc.
> >
>
> What do you mean by linked list? There's algorithms for LIFO and FIFO
queues.
> If you want random insert and delete it's a bit more complex.
>
> Joe Seigh

Ronald Landheer-Cieslak

7/20/2004 3:56:00 PM

0

Rick wrote:

> Hi,
>
> I am looking for any working source code for a simple lock-free linked list
> that can be compiled and run on Linux and Intel.
>
> Please reply with the URL or if as an attachment, to rickgoh(ADD)yahoo.com.
>
> Example of such lock-free linked list is Timothy Harris's:
> http://www.cl.cam.ac.uk/Research/SRG/netos/...
>
> The website contains the publications and some code/library. However, there
> isn't any lock-free linked list code. Only more complex ones like Skiplist,
> binary search trees, etc.
>
> Many thanks.
>
>
> Regards,
> Rick Goh
>
>
>
Have a look here:
http://jail-ust.sourceforge.net/index.php?section=3&...
and here:
http://cvs.sourceforge.net/v...jail-ust/l...
and here for a double-linked list:
http://cvs.sourceforge.net/v...jail-ust/l...list.c?view=markup
here for the article describing the latter, by M.M. Micheal
http://cvs.sourceforge.net/v...*checkout*/jail-ust/doc/lock-free_lists.pdf
http://www.research.ibm.com/people/m/michael/spa... [original
location]

libcontain also contains a binomial tree implementation, no binary tree
yet, though (feel free to contribute).

HTH

rlc

NB: all the code in libcontain is GPL/BSD double-licensed. Contributers
get a GPL waiver - if you want one, contribute :)

Rick

7/20/2004 6:05:00 PM

0

Hi,
Wow a very interesting project indeed!
Will try out the codes first and get back to you if I face any problems.
Of course if I am able, I will contribute back to the project. =)
I have read those papers you have mentioned/on your website but unable to
obtain the codes to try out.
Thanks for the tip on the existence of this project.

Rick


"Ronald Landheer-Cieslak" <ronald@landheer.com> wrote in message
news:2m4tkvFj5831U1@uni-berlin.de...
> Rick wrote:
>
> > Hi,
> >
> > I am looking for any working source code for a simple lock-free linked
list
> > that can be compiled and run on Linux and Intel.
> >
> > Please reply with the URL or if as an attachment, to
rickgoh(ADD)yahoo.com.
> >
> > Example of such lock-free linked list is Timothy Harris's:
> > http://www.cl.cam.ac.uk/Research/SRG/netos/...
> >
> > The website contains the publications and some code/library. However,
there
> > isn't any lock-free linked list code. Only more complex ones like
Skiplist,
> > binary search trees, etc.
> >
> > Many thanks.
> >
> >
> > Regards,
> > Rick Goh
> >
> >
> >
> Have a look here:
> http://jail-ust.sourceforge.net/index.php?section=3&...
> and here:
> http://cvs.sourceforge.net/v...jail-ust/l...
> and here for a double-linked list:
>
http://cvs.sourceforge.net/v...jail-ust/l...list.c?view=markup
> here for the article describing the latter, by M.M. Micheal
>
http://cvs.sourceforge.net/v...*checkout*/jail-ust/doc/lock-free_lists.pdf
> http://www.research.ibm.com/people/m/michael/spa... [original
> location]
>
> libcontain also contains a binomial tree implementation, no binary tree
> yet, though (feel free to contribute).
>
> HTH
>
> rlc
>
> NB: all the code in libcontain is GPL/BSD double-licensed. Contributers
> get a GPL waiver - if you want one, contribute :)

Mouse

7/20/2004 9:52:00 PM

0

> http://www.research.ibm.com/people/m/michael/spa... [original
> location]

This is a nice algo.

Many different types of garbage collectors fit right in with it... ibm
freelist, user or kernel space RCU, atomic_ptr, my proxy gc, SMR, ect...

Ronald Landheer-Cieslak

7/21/2004 1:19:00 PM

0

SenderX wrote:

>>http://www.research.ibm.com/people/m/michael/spa... [original
>>location]
>
>
> This is a nice algo.
>
> Many different types of garbage collectors fit right in with it... ibm
> freelist, user or kernel space RCU, atomic_ptr, my proxy gc, SMR, ect...
>
>
Yeah.. My implementation uses SMR, but it should be pretty
straight-forward to adapt it for using RCU (which makes sense for a
linked list) or pretty much any other garbage collector - just find the
hptr_* and insert something else :)

(OK, it might not be *that* easy, but you get the point ;) )

rlc

Rick

7/27/2004 3:13:00 PM

0

Dear Ronald,

After several attempts, I am still unable to install JAIL properly.

Upon installation:
./configure
make
make install
There were no errors except for a few in which the libmemory/arch is missing
the include folder as well as the config.arch file.

I then try to recompile some test files. All of them seem to have linker
problems:

E.g.
in libmemory/test1.c
when i do a: gcc test1.c,
I get this:

/home/rickgoh/tmp/ccMbBWZy.o(.text+0x16): In function `main':
: undefined reference to `smr_init'
/home/rickgoh/tmp/ccMbBWZy.o(.text+0x23): In function `main':
: undefined reference to `smr_malloc'
/home/rickgoh/tmp/ccMbBWZy.o(.text+0x34): In function `main':
: undefined reference to `smr_free'
/home/rickgoh/tmp/ccMbBWZy.o(.text+0x41): In function `main':
: undefined reference to `smr_malloc'
/home/rickgoh/tmp/ccMbBWZy.o(.text+0x52): In function `main':
: undefined reference to `smr_free'

Please advise.



"Rick" <NOSPAM_rickgoh@yahoo.com> wrote in message
news:40fd5f3b$1@news.starhub.net.sg...
> Hi,
> Wow a very interesting project indeed!
> Will try out the codes first and get back to you if I face any problems.
> Of course if I am able, I will contribute back to the project. =)
> I have read those papers you have mentioned/on your website but unable to
> obtain the codes to try out.
> Thanks for the tip on the existence of this project.
>
> Rick
>
>
> "Ronald Landheer-Cieslak" <ronald@landheer.com> wrote in message
> news:2m4tkvFj5831U1@uni-berlin.de...
> > Rick wrote:
> >
> > > Hi,
> > >
> > > I am looking for any working source code for a simple lock-free linked
> list
> > > that can be compiled and run on Linux and Intel.
> > >
> > > Please reply with the URL or if as an attachment, to
> rickgoh(ADD)yahoo.com.
> > >
> > > Example of such lock-free linked list is Timothy Harris's:
> > > http://www.cl.cam.ac.uk/Research/SRG/netos/...
> > >
> > > The website contains the publications and some code/library. However,
> there
> > > isn't any lock-free linked list code. Only more complex ones like
> Skiplist,
> > > binary search trees, etc.
> > >
> > > Many thanks.
> > >
> > >
> > > Regards,
> > > Rick Goh
> > >
> > >
> > >
> > Have a look here:
> > http://jail-ust.sourceforge.net/index.php?section=3&...
> > and here:
> > http://cvs.sourceforge.net/v...jail-ust/l...
> > and here for a double-linked list:
> >
>
http://cvs.sourceforge.net/v...jail-ust/l...list.c?view=markup
> > here for the article describing the latter, by M.M. Micheal
> >
>
http://cvs.sourceforge.net/v...*checkout*/jail-ust/doc/lock-free_lists.pdf
> > http://www.research.ibm.com/people/m/michael/spa... [original
> > location]
> >
> > libcontain also contains a binomial tree implementation, no binary tree
> > yet, though (feel free to contribute).
> >
> > HTH
> >
> > rlc
> >
> > NB: all the code in libcontain is GPL/BSD double-licensed. Contributers
> > get a GPL waiver - if you want one, contribute :)
>
>

Ronald Landheer-Cieslak

7/27/2004 5:58:00 PM

0

Rick wrote:
> Dear Ronald,
>
> After several attempts, I am still unable to install JAIL properly.
>
> Upon installation:
> ./configure
> make
> make install
> There were no errors except for a few in which the libmemory/arch is missing
> the include folder as well as the config.arch file.
>
> I then try to recompile some test files. All of them seem to have linker
> problems:
>
> E.g.
> in libmemory/test1.c
> when i do a: gcc test1.c,
> I get this:
>
> /home/rickgoh/tmp/ccMbBWZy.o(.text+0x16): In function `main':
> : undefined reference to `smr_init'
> /home/rickgoh/tmp/ccMbBWZy.o(.text+0x23): In function `main':
> : undefined reference to `smr_malloc'
> /home/rickgoh/tmp/ccMbBWZy.o(.text+0x34): In function `main':
> : undefined reference to `smr_free'
> /home/rickgoh/tmp/ccMbBWZy.o(.text+0x41): In function `main':
> : undefined reference to `smr_malloc'
> /home/rickgoh/tmp/ccMbBWZy.o(.text+0x52): In function `main':
> : undefined reference to `smr_free'
>
> Please advise.
The libmemory test files need libmemory - smr_free is an entry point in
the libmemory library, as is smr_malloc, smr_init, etc. Hence, to build
the programs you'll have to link with the already-built libmemory.

If parts of the arch directory tree are missing (which is possible: the
released configury had problems which is why I'm replacing it at the
moment) your build probably won't work.

The libcontain-0.2-alpha1 archive does contain the arch tree, so you
could just copy it from there (they're the same files).

Otherwise, if you want to hand-build the tests, you will have to build
the library first and link with it. (See the -l option of gcc).

If you want more specific help, I'll probably have to know what platform
you're on, etc., but that would be OT on this group. Mail to
jail-ust-devel at lists dot sourceforge dot net in that case (you'll
have to subscribe to be able to mail).

rlc

NB: when I'm done updating the configury, I'll wrap up a new libmemory
distro that should compile OOTB..