From owner-freebsd-current@FreeBSD.ORG Thu Apr 2 10:00:26 2009 Return-Path: Delivered-To: current@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id CA1AC1065675 for ; Thu, 2 Apr 2009 10:00:26 +0000 (UTC) (envelope-from sobomax@FreeBSD.org) Received: from sippysoft.com (gk1.360sip.com [72.236.70.240]) by mx1.freebsd.org (Postfix) with ESMTP id 761678FC14 for ; Thu, 2 Apr 2009 10:00:26 +0000 (UTC) (envelope-from sobomax@FreeBSD.org) Received: from [192.168.1.38] (S0106001372fd1e07.vs.shawcable.net [70.71.171.106]) (authenticated bits=0) by sippysoft.com (8.14.3/8.14.3) with ESMTP id n32A0OU5074325 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 2 Apr 2009 03:00:25 -0700 (PDT) (envelope-from sobomax@FreeBSD.org) Message-ID: <49D48CA7.9050102@FreeBSD.org> Date: Thu, 02 Apr 2009 03:00:07 -0700 From: Maxim Sobolev Organization: Sippy Software, Inc. User-Agent: Thunderbird 2.0.0.21 (Windows/20090302) MIME-Version: 1.0 To: Luigi Rizzo References: <20090402070605.GA96848@onelab2.iet.unipi.it> <20090402084833.GZ31897@deviant.kiev.zoral.com.ua> <20090402085854.GA2237@onelab2.iet.unipi.it> In-Reply-To: <20090402085854.GA2237@onelab2.iet.unipi.it> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: Kostik Belousov , current@FreeBSD.org Subject: Re: cmpxchg / atomic_cmpset_int emulation for userland (i386) ? X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 02 Apr 2009 10:00:28 -0000 Luigi Rizzo wrote: > On Thu, Apr 02, 2009 at 11:48:33AM +0300, Kostik Belousov wrote: >> On Thu, Apr 02, 2009 at 09:06:05AM +0200, Luigi Rizzo wrote: >>> Hi, >>> I have some list manipulation algorithm that I would like to use >>> that relies rather centrally on atomic_cmpset_int(). >>> >>> This is an atomic instruction on 486+, but not available on 386 >>> and maybe other platforms. i386/atomic.h has a replacement >>> but it uses "pushfl; cli; ... popfl;" so it cannot run in userland. >>> >>> I was wondering if there is a good emulation for that instruction >>> on the i386 that is suitable for userland (other architectures >>> we support have a CPU instruction that does it, or in the case of ARM, >>> a usable emulation for userland). >> FreeBSD cannot boot on anything < 486, i.e. cmpxchgl and xaddl may be >> considered always supported by the CPU. > > It was a slightly more generic question -- this stuff is for userland > so while we can assume it works on modern FreeBSD versions, I would > like to see what constraints it has on older versions of FreeBSD. > Of course I can emulate the critical section with a pthread lock, > but that would be the worst case option. On i386's you can use XCHG instruction to implement locks and test&set in userland. Check this: http://lists.canonical.org/pipermail/kragen-tol/1999-August/000457.html http://www.acm.uiuc.edu/sigops/roll_your_own/i386/atomic.html The simplest is the XCHG instruction, which can be used to atomically exchange two registers or a register and a memory location. This makes it possible to implement multiple exclusion; reserve a particular location in RAM as a mutex, and initially set it to 1. To acquire the mutex, set a register to 0, and XCHG it with the location in RAM. If what you get back is a 1, then you have successfully acquired the mutex; otherwise, someone else has it. You can return the mutex simply by setting the location to a nonzero value. Intel's doc says, "When a memory operand is used with the XCHG instruction, the processor's LOCK signal is automatically asserted. This instruction is thus useful for implementing semaphores or similar data structures for process synchronization." -Maxim