Tue Dec 3 21:11:39 2024
EVENTS
 FREE
SOFTWARE
INSTITUTE

POLITICS
JOBS
MEMBERS'
CORNER

MAILING
LIST

NYLXS Mailing Lists and Archives
NYLXS Members have a lot to say and share but we don't keep many secrets. Join the Hangout Mailing List and say your peice.

DATE 2015-05-01

LEARN

2024-12-03 | 2024-11-03 | 2024-10-03 | 2024-09-03 | 2024-08-03 | 2024-07-03 | 2024-06-03 | 2024-05-03 | 2024-04-03 | 2024-03-03 | 2024-02-03 | 2024-01-03 | 2023-12-03 | 2023-11-03 | 2023-10-03 | 2023-09-03 | 2023-08-03 | 2023-07-03 | 2023-06-03 | 2023-05-03 | 2023-04-03 | 2023-03-03 | 2023-02-03 | 2023-01-03 | 2022-12-03 | 2022-11-03 | 2022-10-03 | 2022-09-03 | 2022-08-03 | 2022-07-03 | 2022-06-03 | 2022-05-03 | 2022-04-03 | 2022-03-03 | 2022-02-03 | 2022-01-03 | 2021-12-03 | 2021-11-03 | 2021-10-03 | 2021-09-03 | 2021-08-03 | 2021-07-03 | 2021-06-03 | 2021-05-03 | 2021-04-03 | 2021-03-03 | 2021-02-03 | 2021-01-03 | 2020-12-03 | 2020-11-03 | 2020-10-03 | 2020-09-03 | 2020-08-03 | 2020-07-03 | 2020-06-03 | 2020-05-03 | 2020-04-03 | 2020-03-03 | 2020-02-03 | 2020-01-03 | 2019-12-03 | 2019-11-03 | 2019-10-03 | 2019-09-03 | 2019-08-03 | 2019-07-03 | 2019-06-03 | 2019-05-03 | 2019-04-03 | 2019-03-03 | 2019-02-03 | 2019-01-03 | 2018-12-03 | 2018-11-03 | 2018-10-03 | 2018-09-03 | 2018-08-03 | 2018-07-03 | 2018-06-03 | 2018-05-03 | 2018-04-03 | 2018-03-03 | 2018-02-03 | 2018-01-03 | 2017-12-03 | 2017-11-03 | 2017-10-03 | 2017-09-03 | 2017-08-03 | 2017-07-03 | 2017-06-03 | 2017-05-03 | 2017-04-03 | 2017-03-03 | 2017-02-03 | 2017-01-03 | 2016-12-03 | 2016-11-03 | 2016-10-03 | 2016-09-03 | 2016-08-03 | 2016-07-03 | 2016-06-03 | 2016-05-03 | 2016-04-03 | 2016-03-03 | 2016-02-03 | 2016-01-03 | 2015-12-03 | 2015-11-03 | 2015-10-03 | 2015-09-03 | 2015-08-03 | 2015-07-03 | 2015-06-03 | 2015-05-03 | 2015-04-03 | 2015-03-03 | 2015-02-03 | 2015-01-03 | 2014-12-03 | 2014-11-03 | 2014-10-03

Key: Value:

Key: Value:

MESSAGE
DATE 2015-05-02
FROM Ruben Safir
SUBJECT Subject: [LIU Comp Sci] Great Article on Software Concordance program writing
From owner-learn-outgoing-at-mrbrklyn.com Sat May 2 21:28:39 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 77DAE161166; Sat, 2 May 2015 21:28:39 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id 6622E161162; Sat, 2 May 2015 21:28:39 -0400 (EDT)
Delivered-To: learn-at-nylxs.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id 4B40A161130;
Sat, 2 May 2015 21:28:14 -0400 (EDT)
Received: from [10.0.0.19] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 2965D1250C;
Sat, 2 May 2015 21:28:14 -0400 (EDT)
Message-ID: <554579AD.1040205-at-panix.com>
Date: Sat, 02 May 2015 21:28:13 -0400
From: Ruben Safir
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: learn-at-nylxs.com, Hangout
Subject: [LIU Comp Sci] Great Article on Software Concordance program writing
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Sender: owner-learn-at-mrbrklyn.com
Precedence: bulk
Reply-To: learn-at-mrbrklyn.com

http://www.linuxjournal.com/article/5833


just the first page


Kernel Locking Techniques

Issue 100

From Issue #100
August 2002

Aug 01, 2002 By Robert Love
in

* SysAdmin

Robert explains the various locking primitives in the Linux kernel, why
you need them and how kernel developers can use them to write safe code.

Proper locking can be tough—real tough. Improper locking can result in
random crashes and other oddities. Poorly designed locking can result in
code that is hard to read, performs poorly and makes your fellow kernel
developers cringe. In this article, I explain why kernel code requires
locking, provide general rules for proper kernel locking semantics and
then outline the various locking primitives in the Linux kernel.

Why Do We Need Locking in the Kernel?

The fundamental issue surrounding locking is the need to provide
synchronization in certain code paths in the kernel. These code paths,
called critical sections, require some combination of concurrency or
re-entrancy protection and proper ordering with respect to other events.
The typical result without proper locking is called a race condition.
Realize how even a simple i++ is dangerous if i is shared! Consider the
case where one processor reads i, then another, then they both increment
it, then they both write i back to memory. If i were originally 2, it
should now be 4, but in fact it would be 3!

This is not to say that the only locking issues arise from SMP
(symmetric multiprocessing). Interrupt handlers create locking issues,
as does the new preemptible kernel, and any code can block (go to
sleep). Of these, only SMP is considered true concurrency, i.e., only
with SMP can two things actually occur at the exact same time. The other
situations—interrupt handlers, preempt-kernel and blocking
methods—provide pseudo concurrency as code is not actually executed
concurrently, but separate code can mangle one another's data.

These critical regions require locking. The Linux kernel provides a
family of locking primitives that developers can use to write safe and
efficient code.

SMP Locks in a Uniprocessor Kernel

Whether or not you have an SMP machine, people who use your code may.
Further, code that does not handle locking issues properly is typically
not accepted into the Linux kernel. Finally, with a preemptible kernel
even UP (uniprocessor) systems require proper locking. Thus, do not
forget: you must implement locking.

Thankfully, Linus made the excellent design decision of keeping SMP and
UP kernels distinct. This allows certain locks not to exist at all in a
UP kernel. Different combinations of CONFIG_SMP and CONFIG_PREEMPT
compile in varying lock support. It does not matter, however, to the
developer: lock everything appropriately and all situations will be covered.

Atomic Operators

We cover atomic operators initially for two reasons. First, they are the
simplest of the approaches to kernel synchronization and thus the
easiest to understand and use. Second, the complex locking primitives
are built off them. In this sense, they are the building blocks of the
kernel's locks. Atomic operators are operations, like add and subtract,
which perform in one uninterruptible operation. Consider the previous
example of i++. If we could read i, increment it and write it back to
memory in one uninterruptible operation, the race condition discussed
above would not be an issue. Atomic operators provide these
uninterruptible operations. Two types exist: methods that operate on
integers and methods that operate on bits. The integer operations work
like this:

atomic_t v;
atomic_set(&v, 5); /* v = 5 (atomically) */
atomic_add(3, &v); /* v = v + 3 (atomically) */
atomic_dec(&v); /* v = v - 1 (atomically) */
printf("This will print 7: %d\n", atomic_read(&v));

They are simple. There are, however, little caveats to keep in mind when
using atomics. First, you obviously cannot pass an atomic_t to anything
but one of the atomic operators. Likewise, you cannot pass anything to
an atomic operator except an atomic_t. Finally, because of the
limitations of some architectures, do not expect atomic_t to have more
than 24 usable bits. See the “Function Reference” Sidebar for a list of
all atomic integer operations.

Function Reference


The next group of atomic methods is those that operate on individual
bits. They are simpler than the integer methods because they work on the
standard C data types. For example, consider void set_bit(int nr, void
*addr). This function will atomically set to 1 the “nr-th” bit of the
data pointed to by addr. The atomic bit operators are also listed in the
“Function Reference” Sidebar.

Spinlocks

For anything more complicated than trivial examples like those above, a
more complete locking solution is needed. The most common locking
primitive in the kernel is the spinlock, defined in
include/asm/spinlock.h and include/linux/spinlock.h. The spinlock is a
very simple single-holder lock. If a process attempts to acquire a
spinlock and it is unavailable, the process will keep trying (spinning)
until it can acquire the lock. This simplicity creates a small and fast
lock. The basic use of the spinlock is:

spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;
spin_lock_irqsave(&mr_lock, flags);
/* critical section ... */
spin_unlock_irqrestore(&mr_lock, flags);

The use of spin_lock_irqsave() will disable interrupts locally and
provide the spinlock on SMP. This covers both interrupt and SMP
concurrency issues. With a call to spin_unlock_irqrestore(), interrupts
are restored to the state when the lock was acquired. With a UP kernel,
the above code compiles to the same as:

unsigned long flags;
save_flags(flags);
cli();
/* critical section ... */
restore_flags(flags);

which will provide the needed interrupt concurrency protection without
unneeded SMP protection. Another variant of the spinlock is
spin_lock_irq(). This variant disables and re-enables interrupts
unconditionally, in the same manner as cli() and sti(). For example:

spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;
spin_lock_irq(&mr_lock);
/* critical section ... */
spin_unlock_irq(&mr_lock);

This code is only safe when you know that interrupts were not already
disabled before the acquisition of the lock. As the kernel grows in size
and kernel code paths become increasingly hard to predict, it is
suggested you not use this version unless you really know what you are
doing.

All of the above spinlocks assume the data you are protecting is
accessed in both interrupt handlers and normal kernel code. If you know
your data is unique to user-context kernel code (e.g., a system call),
you can use the basic spin_lock() and spin_unlock() methods that acquire
and release the specified lock without any interaction with interrupts.

A final variation of the spinlock is spin_lock_bh() that implements the
standard spinlock as well as disables softirqs. This is needed when you
have code outside a softirq that is also used inside a softirq. The
corresponding unlock function is naturally spin_unlock_bh().

Note that spinlocks in Linux are not recursive as they may be in other
operating systems. Most consider this a sane design decision as
recursive spinlocks encourage poor code. This does imply, however, that
you must be careful not to re-acquire a spinlock you already hold, or
you will deadlock.

Spinlocks should be used to lock data in situations where the lock is
not held for a long time—recall that a waiting process will spin, doing
nothing, waiting for the lock. (See the “Rules” Sidebar for guidelines
on what is considered a long time.) Thankfully, spinlocks can be used
anywhere. You cannot, however, do anything that will sleep while holding
a spinlock. For example, never call any function that touches user
memory, kmalloc() with the GFP_KERNEL flag, any semaphore functions or
any of the schedule functions while holding a spinlock. You have been
warned.

If you need a lock that is safe to hold for longer periods of time, safe
to sleep with or capable of allowing concurrency to do more than one
process at a time, Linux provides the semaphore.


  1. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] debuging methods
  2. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Excellent article on Virtual Paging and OS memory
  3. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Great Article on Software Concordance program writing
  4. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Semephores and what the heck are those things?
  5. 2015-05-03 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Go Language tutorials
  6. 2015-05-04 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] ACL and beyound security in linux
  7. 2015-05-04 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: [Perlweekly] #197 - YAPC::EU Master classes - talks - hackathons
  8. 2015-05-05 Ruben <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] Fibonacci trees
  9. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Examination Question for Allogorthims
  10. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fibonacci trees
  11. 2015-05-05 Ruben <ruben.safir-at-my.liu.edu> Subject: [LIU Comp Sci] Fwd: Internships with Oracle, Amtrak, The Nature Conservancy & more
  12. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Nice possible project for NYLXS or others
  13. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  14. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  15. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  16. 2015-05-06 Ruben <ruben.safir-at-my.liu.edu> Subject: [LIU Comp Sci] Fwd: Re: [opensuse] Re: no space left on the device
  17. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] hashing multiplication
  18. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Kernel Scheduling and wait queues
  19. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: Kernel Scheduler and wiat queues
  20. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: [NYLXS - HANGOUT] Things to study over the summer
  21. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Things to study over the summer
  22. 2015-05-10 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  23. 2015-05-10 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] scheduler Slides
  24. 2015-05-11 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] scheduler Slides
  25. 2015-05-11 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] scheduler Slides
  26. 2015-05-11 Justin Lau <justinml-at-gmail.com> Re: [LIU Comp Sci] scheduler Slides
  27. 2015-05-11 Justin Lau <justinml-at-gmail.com> Re: [LIU Comp Sci] scheduler Slides
  28. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  29. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  30. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  31. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Job sound like this evenings lectures
  32. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] jobs
  33. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] LAMP Jobs
  34. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] April Journal is Available
  35. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Tomorrow: You and 256 others are going to "Btrfs"
  36. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Malloc systemtap probes: an example
  37. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Stackiq - Educational Program
  38. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Student Lab and Club House
  39. 2015-05-13 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [member-at-linkedin.com: RE: April Journal is Available]
  40. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] [mrbrklyn-at-panix.com: Re: [NYLXS - HANGOUT] Things to study over the
  41. 2015-05-14 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Weekly Education Meeting
  42. 2015-05-18 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [jkeen-at-verizon.net: ny.pm Technical Meeting Wed May 20 6:15 pm]
  43. 2015-05-25 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Summer NYLXS Study Schedule
  44. 2015-05-28 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  45. 2015-05-28 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  46. 2015-05-28 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  47. 2015-05-28 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  48. 2015-05-28 Ruben <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: Programming Position
  49. 2015-05-28 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [ruben-at-www.mrbrklyn.com: Linux 1 Book]
  50. 2015-05-31 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule

NYLXS are Do'ers and the first step of Doing is Joining! Join NYLXS and make a difference in your community today!