diff options
Diffstat (limited to 'Documentation')
27 files changed, 2248 insertions, 195 deletions
diff --git a/Documentation/DocBook/Makefile b/Documentation/DocBook/Makefile index 5a2882d275ba..66e1cf733571 100644 --- a/Documentation/DocBook/Makefile +++ b/Documentation/DocBook/Makefile @@ -10,7 +10,8 @@ DOCBOOKS := wanbook.xml z8530book.xml mcabook.xml videobook.xml \ kernel-hacking.xml kernel-locking.xml deviceiobook.xml \ procfs-guide.xml writing_usb_driver.xml \ kernel-api.xml journal-api.xml lsm.xml usb.xml \ - gadget.xml libata.xml mtdnand.xml librs.xml rapidio.xml + gadget.xml libata.xml mtdnand.xml librs.xml rapidio.xml \ + genericirq.xml ### # The build process is as follows (targets): diff --git a/Documentation/DocBook/genericirq.tmpl b/Documentation/DocBook/genericirq.tmpl new file mode 100644 index 000000000000..0f4a4b6321e4 --- /dev/null +++ b/Documentation/DocBook/genericirq.tmpl @@ -0,0 +1,474 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.1.2//EN" + "http://www.oasis-open.org/docbook/xml/4.1.2/docbookx.dtd" []> + +<book id="Generic-IRQ-Guide"> + <bookinfo> + <title>Linux generic IRQ handling</title> + + <authorgroup> + <author> + <firstname>Thomas</firstname> + <surname>Gleixner</surname> + <affiliation> + <address> + <email>tglx@linutronix.de</email> + </address> + </affiliation> + </author> + <author> + <firstname>Ingo</firstname> + <surname>Molnar</surname> + <affiliation> + <address> + <email>mingo@elte.hu</email> + </address> + </affiliation> + </author> + </authorgroup> + + <copyright> + <year>2005-2006</year> + <holder>Thomas Gleixner</holder> + </copyright> + <copyright> + <year>2005-2006</year> + <holder>Ingo Molnar</holder> + </copyright> + + <legalnotice> + <para> + This documentation is free software; you can redistribute + it and/or modify it under the terms of the GNU General Public + License version 2 as published by the Free Software Foundation. + </para> + + <para> + 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. + </para> + + <para> + 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 + </para> + + <para> + For more details see the file COPYING in the source + distribution of Linux. + </para> + </legalnotice> + </bookinfo> + +<toc></toc> + + <chapter id="intro"> + <title>Introduction</title> + <para> + The generic interrupt handling layer is designed to provide a + complete abstraction of interrupt handling for device drivers. + It is able to handle all the different types of interrupt controller + hardware. Device drivers use generic API functions to request, enable, + disable and free interrupts. The drivers do not have to know anything + about interrupt hardware details, so they can be used on different + platforms without code changes. + </para> + <para> + This documentation is provided to developers who want to implement + an interrupt subsystem based for their architecture, with the help + of the generic IRQ handling layer. + </para> + </chapter> + + <chapter id="rationale"> + <title>Rationale</title> + <para> + The original implementation of interrupt handling in Linux is using + the __do_IRQ() super-handler, which is able to deal with every + type of interrupt logic. + </para> + <para> + Originally, Russell King identified different types of handlers to + build a quite universal set for the ARM interrupt handler + implementation in Linux 2.5/2.6. He distinguished between: + <itemizedlist> + <listitem><para>Level type</para></listitem> + <listitem><para>Edge type</para></listitem> + <listitem><para>Simple type</para></listitem> + </itemizedlist> + In the SMP world of the __do_IRQ() super-handler another type + was identified: + <itemizedlist> + <listitem><para>Per CPU type</para></listitem> + </itemizedlist> + </para> + <para> + This split implementation of highlevel IRQ handlers allows us to + optimize the flow of the interrupt handling for each specific + interrupt type. This reduces complexity in that particular codepath + and allows the optimized handling of a given type. + </para> + <para> + The original general IRQ implementation used hw_interrupt_type + structures and their ->ack(), ->end() [etc.] callbacks to + differentiate the flow control in the super-handler. This leads to + a mix of flow logic and lowlevel hardware logic, and it also leads + to unnecessary code duplication: for example in i386, there is a + ioapic_level_irq and a ioapic_edge_irq irq-type which share many + of the lowlevel details but have different flow handling. + </para> + <para> + A more natural abstraction is the clean separation of the + 'irq flow' and the 'chip details'. + </para> + <para> + Analysing a couple of architecture's IRQ subsystem implementations + reveals that most of them can use a generic set of 'irq flow' + methods and only need to add the chip level specific code. + The separation is also valuable for (sub)architectures + which need specific quirks in the irq flow itself but not in the + chip-details - and thus provides a more transparent IRQ subsystem + design. + </para> + <para> + Each interrupt descriptor is assigned its own highlevel flow + handler, which is normally one of the generic + implementations. (This highlevel flow handler implementation also + makes it simple to provide demultiplexing handlers which can be + found in embedded platforms on various architectures.) + </para> + <para> + The separation makes the generic interrupt handling layer more + flexible and extensible. For example, an (sub)architecture can + use a generic irq-flow implementation for 'level type' interrupts + and add a (sub)architecture specific 'edge type' implementation. + </para> + <para> + To make the transition to the new model easier and prevent the + breakage of existing implementations, the __do_IRQ() super-handler + is still available. This leads to a kind of duality for the time + being. Over time the new model should be used in more and more + architectures, as it enables smaller and cleaner IRQ subsystems. + </para> + </chapter> + <chapter id="bugs"> + <title>Known Bugs And Assumptions</title> + <para> + None (knock on wood). + </para> + </chapter> + + <chapter id="Abstraction"> + <title>Abstraction layers</title> + <para> + There are three main levels of abstraction in the interrupt code: + <orderedlist> + <listitem><para>Highlevel driver API</para></listitem> + <listitem><para>Highlevel IRQ flow handlers</para></listitem> + <listitem><para>Chiplevel hardware encapsulation</para></listitem> + </orderedlist> + </para> + <sect1> + <title>Interrupt control flow</title> + <para> + Each interrupt is described by an interrupt descriptor structure + irq_desc. The interrupt is referenced by an 'unsigned int' numeric + value which selects the corresponding interrupt decription structure + in the descriptor structures array. + The descriptor structure contains status information and pointers + to the interrupt flow method and the interrupt chip structure + which are assigned to this interrupt. + </para> + <para> + Whenever an interrupt triggers, the lowlevel arch code calls into + the generic interrupt code by calling desc->handle_irq(). + This highlevel IRQ handling function only uses desc->chip primitives + referenced by the assigned chip descriptor structure. + </para> + </sect1> + <sect1> + <title>Highlevel Driver API</title> + <para> + The highlevel Driver API consists of following functions: + <itemizedlist> + <listitem><para>request_irq()</para></listitem> + <listitem><para>free_irq()</para></listitem> + <listitem><para>disable_irq()</para></listitem> + <listitem><para>enable_irq()</para></listitem> + <listitem><para>disable_irq_nosync() (SMP only)</para></listitem> + <listitem><para>synchronize_irq() (SMP only)</para></listitem> + <listitem><para>set_irq_type()</para></listitem> + <listitem><para>set_irq_wake()</para></listitem> + <listitem><para>set_irq_data()</para></listitem> + <listitem><para>set_irq_chip()</para></listitem> + <listitem><para>set_irq_chip_data()</para></listitem> + </itemizedlist> + See the autogenerated function documentation for details. + </para> + </sect1> + <sect1> + <title>Highlevel IRQ flow handlers</title> + <para> + The generic layer provides a set of pre-defined irq-flow methods: + <itemizedlist> + <listitem><para>handle_level_irq</para></listitem> + <listitem><para>handle_edge_irq</para></listitem> + <listitem><para>handle_simple_irq</para></listitem> + <listitem><para>handle_percpu_irq</para></listitem> + </itemizedlist> + The interrupt flow handlers (either predefined or architecture + specific) are assigned to specific interrupts by the architecture + either during bootup or during device initialization. + </para> + <sect2> + <title>Default flow implementations</title> + <sect3> + <title>Helper functions</title> + <para> + The helper functions call the chip primitives and + are used by the default flow implementations. + The following helper functions are implemented (simplified excerpt): + <programlisting> +default_enable(irq) +{ + desc->chip->unmask(irq); +} + +default_disable(irq) +{ + if (!delay_disable(irq)) + desc->chip->mask(irq); +} + +default_ack(irq) +{ + chip->ack(irq); +} + +default_mask_ack(irq) +{ + if (chip->mask_ack) { + chip->mask_ack(irq); + } else { + chip->mask(irq); + chip->ack(irq); + } +} + +noop(irq) +{ +} + + </programlisting> + </para> + </sect3> + </sect2> + <sect2> + <title>Default flow handler implementations</title> + <sect3> + <title>Default Level IRQ flow handler</title> + <para> + handle_level_irq provides a generic implementation + for level-triggered interrupts. + </para> + <para> + The following control flow is implemented (simplified excerpt): + <programlisting> +desc->chip->start(); +handle_IRQ_event(desc->action); +desc->chip->end(); + </programlisting> + </para> + </sect3> + <sect3> + <title>Default Edge IRQ flow handler</title> + <para> + handle_edge_irq provides a generic implementation + for edge-triggered interrupts. + </para> + <para> + The following control flow is implemented (simplified excerpt): + <programlisting> +if (desc->status & running) { + desc->chip->hold(); + desc->status |= pending | masked; + return; +} +desc->chip->start(); +desc->status |= running; +do { + if (desc->status & masked) + desc->chip->enable(); + desc-status &= ~pending; + handle_IRQ_event(desc->action); +} while (status & pending); +desc-status &= ~running; +desc->chip->end(); + </programlisting> + </para> + </sect3> + <sect3> + <title>Default simple IRQ flow handler</title> + <para> + handle_simple_irq provides a generic implementation + for simple interrupts. + </para> + <para> + Note: The simple flow handler does not call any + handler/chip primitives. + </para> + <para> + The following control flow is implemented (simplified excerpt): + <programlisting> +handle_IRQ_event(desc->action); + </programlisting> + </para> + </sect3> + <sect3> + <title>Default per CPU flow handler</title> + <para> + handle_percpu_irq provides a generic implementation + for per CPU interrupts. + </para> + <para> + Per CPU interrupts are only available on SMP and + the handler provides a simplified version without + locking. + </para> + <para> + The following control flow is implemented (simplified excerpt): + <programlisting> +desc->chip->start(); +handle_IRQ_event(desc->action); +desc->chip->end(); + </programlisting> + </para> + </sect3> + </sect2> + <sect2> + <title>Quirks and optimizations</title> + <para> + The generic functions are intended for 'clean' architectures and chips, + which have no platform-specific IRQ handling quirks. If an architecture + needs to implement quirks on the 'flow' level then it can do so by + overriding the highlevel irq-flow handler. + </para> + </sect2> + <sect2> + <title>Delayed interrupt disable</title> + <para> + This per interrupt selectable feature, which was introduced by Russell + King in the ARM interrupt implementation, does not mask an interrupt + at the hardware level when disable_irq() is called. The interrupt is + kept enabled and is masked in the flow handler when an interrupt event + happens. This prevents losing edge interrupts on hardware which does + not store an edge interrupt event while the interrupt is disabled at + the hardware level. When an interrupt arrives while the IRQ_DISABLED + flag is set, then the interrupt is masked at the hardware level and + the IRQ_PENDING bit is set. When the interrupt is re-enabled by + enable_irq() the pending bit is checked and if it is set, the + interrupt is resent either via hardware or by a software resend + mechanism. (It's necessary to enable CONFIG_HARDIRQS_SW_RESEND when + you want to use the delayed interrupt disable feature and your + hardware is not capable of retriggering an interrupt.) + The delayed interrupt disable can be runtime enabled, per interrupt, + by setting the IRQ_DELAYED_DISABLE flag in the irq_desc status field. + </para> + </sect2> + </sect1> + <sect1> + <title>Chiplevel hardware encapsulation</title> + <para> + The chip level hardware descriptor structure irq_chip + contains all the direct chip relevant functions, which + can be utilized by the irq flow implementations. + <itemizedlist> + <listitem><para>ack()</para></listitem> + <listitem><para>mask_ack() - Optional, recommended for performance</para></listitem> + <listitem><para>mask()</para></listitem> + <listitem><para>unmask()</para></listitem> + <listitem><para>retrigger() - Optional</para></listitem> + <listitem><para>set_type() - Optional</para></listitem> + <listitem><para>set_wake() - Optional</para></listitem> + </itemizedlist> + These primitives are strictly intended to mean what they say: ack means + ACK, masking means masking of an IRQ line, etc. It is up to the flow + handler(s) to use these basic units of lowlevel functionality. + </para> + </sect1> + </chapter> + + <chapter id="doirq"> + <title>__do_IRQ entry point</title> + <para> + The original implementation __do_IRQ() is an alternative entry + point for all types of interrupts. + </para> + <para> + This handler turned out to be not suitable for all + interrupt hardware and was therefore reimplemented with split + functionality for egde/level/simple/percpu interrupts. This is not + only a functional optimization. It also shortens code paths for + interrupts. + </para> + <para> + To make use of the split implementation, replace the call to + __do_IRQ by a call to desc->chip->handle_irq() and associate + the appropriate handler function to desc->chip->handle_irq(). + In most cases the generic handler implementations should + be sufficient. + </para> + </chapter> + + <chapter id="locking"> + <title>Locking on SMP</title> + <para> + The locking of chip registers is up to the architecture that + defines the chip primitives. There is a chip->lock field that can be used + for serialization, but the generic layer does not touch it. The per-irq + structure is protected via desc->lock, by the generic layer. + </para> + </chapter> + <chapter id="structs"> + <title>Structures</title> + <para> + This chapter contains the autogenerated documentation of the structures which are + used in the generic IRQ layer. + </para> +!Iinclude/linux/irq.h + </chapter> + + <chapter id="pubfunctions"> + <title>Public Functions Provided</title> + <para> + This chapter contains the autogenerated documentation of the kernel API functions + which are exported. + </para> +!Ekernel/irq/manage.c +!Ekernel/irq/chip.c + </chapter> + + <chapter id="intfunctions"> + <title>Internal Functions Provided</title> + <para> + This chapter contains the autogenerated documentation of the internal functions. + </para> +!Ikernel/irq/handle.c +!Ikernel/irq/chip.c + </chapter> + + <chapter id="credits"> + <title>Credits</title> + <para> + The following people have contributed to this document: + <orderedlist> + <listitem><para>Thomas Gleixner<email>tglx@linutronix.de</email></para></listitem> + <listitem><para>Ingo Molnar<email>mingo@elte.hu</email></para></listitem> + </orderedlist> + </para> + </chapter> +</book> diff --git a/Documentation/DocBook/kernel-locking.tmpl b/Documentation/DocBook/kernel-locking.tmpl index 158ffe9bfade..644c3884fab9 100644 --- a/Documentation/DocBook/kernel-locking.tmpl +++ b/Documentation/DocBook/kernel-locking.tmpl @@ -1590,7 +1590,7 @@ the amount of locking which needs to be done. <para> Our final dilemma is this: when can we actually destroy the removed element? Remember, a reader might be stepping through - this element in the list right now: it we free this element and + this element in the list right now: if we free this element and the <symbol>next</symbol> pointer changes, the reader will jump off into garbage and crash. We need to wait until we know that all the readers who were traversing the list when we deleted the diff --git a/Documentation/IRQ.txt b/Documentation/IRQ.txt new file mode 100644 index 000000000000..1011e7175021 --- /dev/null +++ b/Documentation/IRQ.txt @@ -0,0 +1,22 @@ +What is an IRQ? + +An IRQ is an interrupt request from a device. +Currently they can come in over a pin, or over a packet. +Several devices may be connected to the same pin thus +sharing an IRQ. + +An IRQ number is a kernel identifier used to talk about a hardware +interrupt source. Typically this is an index into the global irq_desc +array, but except for what linux/interrupt.h implements the details +are architecture specific. + +An IRQ number is an enumeration of the possible interrupt sources on a +machine. Typically what is enumerated is the number of input pins on +all of the interrupt controller in the system. In the case of ISA +what is enumerated are the 16 input pins on the two i8259 interrupt +controllers. + +Architectures can assign additional meaning to the IRQ numbers, and +are encouraged to in the case where there is any manual configuration +of the hardware involved. The ISA IRQs are a classic example of +assigning this kind of additional meaning. diff --git a/Documentation/RCU/torture.txt b/Documentation/RCU/torture.txt index e4c38152f7f7..a4948591607d 100644 --- a/Documentation/RCU/torture.txt +++ b/Documentation/RCU/torture.txt @@ -7,7 +7,7 @@ The CONFIG_RCU_TORTURE_TEST config option is available for all RCU implementations. It creates an rcutorture kernel module that can be loaded to run a torture test. The test periodically outputs status messages via printk(), which can be examined via the dmesg -command (perhaps grepping for "rcutorture"). The test is started +command (perhaps grepping for "torture"). The test is started when the module is loaded, and stops when the module is unloaded. However, actually setting this config option to "y" results in the system @@ -35,6 +35,19 @@ stat_interval The number of seconds between output of torture be printed -only- when the module is unloaded, and this is the default. +shuffle_interval + The number of seconds to keep the test threads affinitied + to a particular subset of the CPUs. Used in conjunction + with test_no_idle_hz. + +test_no_idle_hz Whether or not to test the ability of RCU to operate in + a kernel that disables the scheduling-clock interrupt to + idle CPUs. Boolean parameter, "1" to test, "0" otherwise. + +torture_type The type of RCU to test: "rcu" for the rcu_read_lock() + API, "rcu_bh" for the rcu_read_lock_bh() API, and "srcu" + for the "srcu_read_lock()" API. + verbose Enable debug printk()s. Default is disabled. @@ -42,14 +55,14 @@ OUTPUT The statistics output is as follows: - rcutorture: --- Start of test: nreaders=16 stat_interval=0 verbose=0 - rcutorture: rtc: 0000000000000000 ver: 1916 tfle: 0 rta: 1916 rtaf: 0 rtf: 1915 - rcutorture: Reader Pipe: 1466408 9747 0 0 0 0 0 0 0 0 0 - rcutorture: Reader Batch: 1464477 11678 0 0 0 0 0 0 0 0 - rcutorture: Free-Block Circulation: 1915 1915 1915 1915 1915 1915 1915 1915 1915 1915 0 - rcutorture: --- End of test + rcu-torture: --- Start of test: nreaders=16 stat_interval=0 verbose=0 + rcu-torture: rtc: 0000000000000000 ver: 1916 tfle: 0 rta: 1916 rtaf: 0 rtf: 1915 + rcu-torture: Reader Pipe: 1466408 9747 0 0 0 0 0 0 0 0 0 + rcu-torture: Reader Batch: 1464477 11678 0 0 0 0 0 0 0 0 + rcu-torture: Free-Block Circulation: 1915 1915 1915 1915 1915 1915 1915 1915 1915 1915 0 + rcu-torture: --- End of test -The command "dmesg | grep rcutorture:" will extract this information on +The command "dmesg | grep torture:" will extract this information on most systems. On more esoteric configurations, it may be necessary to use other commands to access the output of the printk()s used by the RCU torture test. The printk()s use KERN_ALERT, so they should @@ -115,8 +128,9 @@ The following script may be used to torture RCU: modprobe rcutorture sleep 100 rmmod rcutorture - dmesg | grep rcutorture: + dmesg | grep torture: The output can be manually inspected for the error flag of "!!!". One could of course create a more elaborate script that automatically -checked for such errors. +checked for such errors. The "rmmod" command forces a "SUCCESS" or +"FAILURE" indication to be printk()ed. diff --git a/Documentation/arm/Samsung-S3C24XX/Overview.txt b/Documentation/arm/Samsung-S3C24XX/Overview.txt index 8c6ee684174c..3e46d2a31158 100644 --- a/Documentation/arm/Samsung-S3C24XX/Overview.txt +++ b/Documentation/arm/Samsung-S3C24XX/Overview.txt @@ -7,11 +7,13 @@ Introduction ------------ The Samsung S3C24XX range of ARM9 System-on-Chip CPUs are supported - by the 's3c2410' architecture of ARM Linux. Currently the S3C2410 and - the S3C2440 are supported CPUs. + by the 's3c2410' architecture of ARM Linux. Currently the S3C2410, + S3C2440 and S3C2442 devices are supported. Support for the S3C2400 series is in progress. + Support for the S3C2412 and S3C2413 CPUs is being merged. + Configuration ------------- @@ -43,9 +45,18 @@ Machines Samsung's own development board, geared for PDA work. + Samsung/Aiji SMDK2412 + + The S3C2412 version of the SMDK2440. + + Samsung/Aiji SMDK2413 + + The S3C2412 version of the SMDK2440. + Samsung/Meritech SMDK2440 - The S3C2440 compatible version of the SMDK2440 + The S3C2440 compatible version of the SMDK2440, which has the + option of an S3C2440 or S3C2442 CPU module. Thorcom VR1000 @@ -211,24 +222,6 @@ Port Contributors Lucas Correia Villa Real (S3C2400 port) -Document Changes ----------------- - - 05 Sep 2004 - BJD - Added Document Changes section - 05 Sep 2004 - BJD - Added Klaus Fetscher to list of contributors - 25 Oct 2004 - BJD - Added Dimitry Andric to list of contributors - 25 Oct 2004 - BJD - Updated the MTD from the 2.6.9 merge - 21 Jan 2005 - BJD - Added rx3715, added Shannon to contributors - 10 Feb 2005 - BJD - Added Guillaume Gourat to contributors - 02 Mar 2005 - BJD - Added SMDK2440 to list of machines - 06 Mar 2005 - BJD - Added Christer Weinigel - 08 Mar 2005 - BJD - Added LCVR to list of people, updated introduction - 08 Mar 2005 - BJD - Added section on adding machines - 09 Sep 2005 - BJD - Added section on platform data - 11 Feb 2006 - BJD - Added I2C, RTC and Watchdog sections - 11 Feb 2006 - BJD - Added Osiris machine, and S3C2400 information - - Document Author --------------- diff --git a/Documentation/arm/Samsung-S3C24XX/S3C2412.txt b/Documentation/arm/Samsung-S3C24XX/S3C2412.txt new file mode 100644 index 000000000000..cb82a7fc7901 --- /dev/null +++ b/Documentation/arm/Samsung-S3C24XX/S3C2412.txt @@ -0,0 +1,120 @@ + S3C2412 ARM Linux Overview + ========================== + +Introduction +------------ + + The S3C2412 is part of the S3C24XX range of ARM9 System-on-Chip CPUs + from Samsung. This part has an ARM926-EJS core, capable of running up + to 266MHz (see data-sheet for more information) + + +Clock +----- + + The core clock code provides a set of clocks to the drivers, and allows + for source selection and a number of other features. + + +Power +----- + + No support for suspend/resume to RAM in the current system. + + +DMA +--- + + No current support for DMA. + + +GPIO +---- + + There is support for setting the GPIO to input/output/special function + and reading or writing to them. + + +UART +---- + + The UART hardware is similar to the S3C2440, and is supported by the + s3c2410 driver in the drivers/serial directory. + + +NAND +---- + + The NAND hardware is similar to the S3C2440, and is supported by the + s3c2410 driver in the drivers/mtd/nand directory. + + +USB Host +-------- + + The USB hardware is similar to the S3C2410, with extended clock source + control. The OHCI portion is supported by the ohci-s3c2410 driver, and + the clock control selection is supported by the core clock code. + + +USB Device +---------- + + No current support in the kernel + + +IRQs +---- + + All the standard, and external interrupt sources are supported. The + extra sub-sources are not yet supported. + + +RTC +--- + + The RTC hardware is similar to the S3C2410, and is supported by the + s3c2410-rtc driver. + + +Watchdog +-------- + + The watchdog harware is the same as the S3C2410, and is supported by + the s3c2410_wdt driver. + + +MMC/SD/SDIO +----------- + + No current support for the MMC/SD/SDIO block. + +IIC +--- + + The IIC hardware is the same as the S3C2410, and is supported by the + i2c-s3c24xx driver. + + +IIS +--- + + No current support for the IIS interface. + + +SPI +--- + + No current support for the SPI interfaces. + + +ATA +--- + + No current support for the on-board ATA block. + + +Document Author +--------------- + +Ben Dooks, (c) 2006 Simtec Electronics diff --git a/Documentation/arm/Samsung-S3C24XX/S3C2413.txt b/Documentation/arm/Samsung-S3C24XX/S3C2413.txt new file mode 100644 index 000000000000..ab2a88858f12 --- /dev/null +++ b/Documentation/arm/Samsung-S3C24XX/S3C2413.txt @@ -0,0 +1,21 @@ + S3C2413 ARM Linux Overview + ========================== + +Introduction +------------ + + The S3C2413 is an extended version of the S3C2412, with an camera + interface and mobile DDR memory support. See the S3C2412 support + documentation for more information. + + +Camera Interface +--------------- + + This block is currently not supported. + + +Document Author +--------------- + +Ben Dooks, (c) 2006 Simtec Electronics diff --git a/Documentation/atomic_ops.txt b/Documentation/atomic_ops.txt index 23a1c2402bcc..2a63d5662a93 100644 --- a/Documentation/atomic_ops.txt +++ b/Documentation/atomic_ops.txt @@ -157,13 +157,13 @@ For example, smp_mb__before_atomic_dec() can be used like so: smp_mb__before_atomic_dec(); atomic_dec(&obj->ref_count); -It makes sure that all memory operations preceeding the atomic_dec() +It makes sure that all memory operations preceding the atomic_dec() call are strongly ordered with respect to the atomic counter -operation. In the above example, it guarentees that the assignment of +operation. In the above example, it guarantees that the assignment of "1" to obj->dead will be globally visible to other cpus before the atomic counter decrement. -Without the explicitl smp_mb__before_atomic_dec() call, the +Without the explicit smp_mb__before_atomic_dec() call, the implementation could legally allow the atomic counter update visible to other cpus before the "obj->dead = 1;" assignment. @@ -173,11 +173,11 @@ ordering with respect to memory operations after an atomic_dec() call (smp_mb__{before,after}_atomic_inc()). A missing memory barrier in the cases where they are required by the -atomic_t implementation above can have disasterous results. Here is -an example, which follows a pattern occuring frequently in the Linux +atomic_t implementation above can have disastrous results. Here is +an example, which follows a pattern occurring frequently in the Linux kernel. It is the use of atomic counters to implement reference counting, and it works such that once the counter falls to zero it can -be guarenteed that no other entity can be accessing the object: +be guaranteed that no other entity can be accessing the object: static void obj_list_add(struct obj *obj) { @@ -291,9 +291,9 @@ to the size of an "unsigned long" C data type, and are least of that size. The endianness of the bits within each "unsigned long" are the native endianness of the cpu. - void set_bit(unsigned long nr, volatils unsigned long *addr); - void clear_bit(unsigned long nr, volatils unsigned long *addr); - void change_bit(unsigned long nr, volatils unsigned long *addr); + void set_bit(unsigned long nr, volatile unsigned long *addr); + void clear_bit(unsigned long nr, volatile unsigned long *addr); + void change_bit(unsigned long nr, volatile unsigned long *addr); These routines set, clear, and change, respectively, the bit number indicated by "nr" on the bit mask pointed to by "ADDR". @@ -301,9 +301,9 @@ indicated by "nr" on the bit mask pointed to by "ADDR". They must execute atomically, yet there are no implicit memory barrier semantics required of these interfaces. - int test_and_set_bit(unsigned long nr, volatils unsigned long *addr); - int test_and_clear_bit(unsigned long nr, volatils unsigned long *addr); - int test_and_change_bit(unsigned long nr, volatils unsigned long *addr); + int test_and_set_bit(unsigned long nr, volatile unsigned long *addr); + int test_and_clear_bit(unsigned long nr, volatile unsigned long *addr); + int test_and_change_bit(unsigned long nr, volatile unsigned long *addr); Like the above, except that these routines return a boolean which indicates whether the changed bit was set _BEFORE_ the atomic bit @@ -335,7 +335,7 @@ subsequent memory operation is made visible. For example: /* ... */; obj->killed = 1; -The implementation of test_and_set_bit() must guarentee that +The implementation of test_and_set_bit() must guarantee that "obj->dead = 1;" is visible to cpus before the atomic memory operation done by test_and_set_bit() becomes visible. Likewise, the atomic memory operation done by test_and_set_bit() must become visible before @@ -474,7 +474,7 @@ Now, as far as memory barriers go, as long as spin_lock() strictly orders all subsequent memory operations (including the cas()) with respect to itself, things will be fine. -Said another way, _atomic_dec_and_lock() must guarentee that +Said another way, _atomic_dec_and_lock() must guarantee that a counter dropping to zero is never made visible before the spinlock being acquired. diff --git a/Documentation/driver-model/overview.txt b/Documentation/driver-model/overview.txt index ac4a7a737e43..2050c9ffc629 100644 --- a/Documentation/driver-model/overview.txt +++ b/Documentation/driver-model/overview.txt @@ -18,7 +18,7 @@ Traditional driver models implemented some sort of tree-like structure (sometimes just a list) for the devices they control. There wasn't any uniformity across the different bus types. -The current driver model provides a comon, uniform data model for describing +The current driver model provides a common, uniform data model for describing a bus and the devices that can appear under the bus. The unified bus model includes a set of common attributes which all busses carry, and a set of common callbacks, such as device discovery during bus probing, bus diff --git a/Documentation/feature-removal-schedule.txt b/Documentation/feature-removal-schedule.txt index ddfd77029597..1cbbb8e28999 100644 --- a/Documentation/feature-removal-schedule.txt +++ b/Documentation/feature-removal-schedule.txt @@ -121,16 +121,6 @@ Who: NeilBrown <neilb@suse.de> --------------------------- -What: au1x00_uart driver -When: January 2006 -Why: The 8250 serial driver now has the ability to deal with the differences - between the standard 8250 family of UARTs and their slightly strange - brother on Alchemy SOCs. The loss of features is not considered an - issue. -Who: Ralf Baechle <ralf@linux-mips.org> - ---------------------------- - What: eepro100 network driver When: January 2007 Why: replaced by the e100 driver @@ -166,6 +156,16 @@ Who: Jean Delvare <khali@linux-fr.org> --------------------------- +What: Unused EXPORT_SYMBOL/EXPORT_SYMBOL_GPL exports + (temporary transition config option provided until then) + The transition config option will also be removed at the same time. +When: before 2.6.19 +Why: Unused symbols are both increasing the size of the kernel binary + and are often a sign of "wrong API" +Who: Arjan van de Ven <arjan@linux.intel.com> + +--------------------------- + What: remove EXPORT_SYMBOL(tasklist_lock) When: August 2006 Files: kernel/fork.c @@ -213,3 +213,47 @@ Why: The interface no longer has any callers left in the kernel. It Who: Nick Piggin <npiggin@suse.de> --------------------------- + +What: Support for the MIPS EV96100 evaluation board +When: September 2006 +Why: Does no longer build since at least November 15, 2003, apparently + no userbase left. +Who: Ralf Baechle <ralf@linux-mips.org> + +--------------------------- + +What: Support for the Momentum / PMC-Sierra Jaguar ATX evaluation board +When: September 2006 +Why: Does no longer build since quite some time, and was never popular, + due to the platform being replaced by successor models. Apparently + no user base left. It also is one of the last users of + WANT_PAGE_VIRTUAL. +Who: Ralf Baechle <ralf@linux-mips.org> + +--------------------------- + +What: Support for the Momentum Ocelot, Ocelot 3, Ocelot C and Ocelot G +When: September 2006 +Why: Some do no longer build and apparently there is no user base left + for these platforms. +Who: Ralf Baechle <ralf@linux-mips.org> + +--------------------------- + +What: Support for MIPS Technologies' Altas and SEAD evaluation board +When: September 2006 +Why: Some do no longer build and apparently there is no user base left + for these platforms. Hardware out of production since several years. +Who: Ralf Baechle <ralf@linux-mips.org> + +--------------------------- + +What: Support for the IT8172-based platforms, ITE 8172G and Globespan IVR +When: September 2006 +Why: Code does no longer build since at least 2.6.0, apparently there is + no user base left for these platforms. Hardware out of production + since several years and hardly a trace of the manufacturer left on + the net. +Who: Ralf Baechle <ralf@linux-mips.org> + +--------------------------- diff --git a/Documentation/kdump/gdbmacros.txt b/Documentation/kdump/gdbmacros.txt index dcf5580380ab..9b9b454b048a 100644 --- a/Documentation/kdump/gdbmacros.txt +++ b/Documentation/kdump/gdbmacros.txt @@ -175,7 +175,7 @@ end document trapinfo Run info threads and lookup pid of thread #1 'trapinfo <pid>' will tell you by which trap & possibly - addresthe kernel paniced. + address the kernel panicked. end diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt index bf5d2cd6a56e..86e9282d1c20 100644 --- a/Documentation/kernel-parameters.txt +++ b/Documentation/kernel-parameters.txt @@ -1665,6 +1665,10 @@ running once the system is up. usbhid.mousepoll= [USBHID] The interval which mice are to be polled at. + vdso= [IA-32] + vdso=1: enable VDSO (default) + vdso=0: disable VDSO mapping + video= [FB] Frame buffer configuration See Documentation/fb/modedb.txt. @@ -1681,9 +1685,14 @@ running once the system is up. decrease the size and leave more room for directly mapped kernel RAM. - vmhalt= [KNL,S390] + vmhalt= [KNL,S390] Perform z/VM CP command after system halt. + Format: <command> + + vmpanic= [KNL,S390] Perform z/VM CP command after kernel panic. + Format: <command> - vmpoff= [KNL,S390] + vmpoff= [KNL,S390] Perform z/VM CP command after power off. + Format: <command> waveartist= [HW,OSS] Format: <io>,<irq>,<dma>,<dma2> diff --git a/Documentation/keys-request-key.txt b/Documentation/keys-request-key.txt index 22488d791168..c1f64fdf84cb 100644 --- a/Documentation/keys-request-key.txt +++ b/Documentation/keys-request-key.txt @@ -3,16 +3,23 @@ =================== The key request service is part of the key retention service (refer to -Documentation/keys.txt). This document explains more fully how that the -requesting algorithm works. +Documentation/keys.txt). This document explains more fully how the requesting +algorithm works. The process starts by either the kernel requesting a service by calling -request_key(): +request_key*(): struct key *request_key(const struct key_type *type, const char *description, const char *callout_string); +or: + + struct key *request_key_with_auxdata(const struct key_type *type, + const char *description, + const char *callout_string, + void *aux); + Or by userspace invoking the request_key system call: key_serial_t request_key(const char *type, @@ -20,16 +27,26 @@ Or by userspace invoking the request_key system call: const char *callout_info, key_serial_t dest_keyring); -The main difference between the two access points is that the in-kernel -interface does not need to link the key to a keyring to prevent it from being -immediately destroyed. The kernel interface returns a pointer directly to the -key, and it's up to the caller to destroy the key. +The main difference between the access points is that the in-kernel interface +does not need to link the key to a keyring to prevent it from being immediately +destroyed. The kernel interface returns a pointer directly to the key, and +it's up to the caller to destroy the key. + +The request_key_with_auxdata() call is like the in-kernel request_key() call, +except that it permits auxiliary data to be passed to the upcaller (the default +is NULL). This is only useful for those key types that define their own upcall +mechanism rather than using /sbin/request-key. The userspace interface links the key to a keyring associated with the process to prevent the key from going away, and returns the serial number of the key to the caller. +The following example assumes that the key types involved don't define their +own upcall mechanisms. If they do, then those should be substituted for the +forking and execution of /sbin/request-key. + + =========== THE PROCESS =========== @@ -40,8 +57,8 @@ A request proceeds in the following manner: interface]. (2) request_key() searches the process's subscribed keyrings to see if there's - a suitable key there. If there is, it returns the key. If there isn't, and - callout_info is not set, an error is returned. Otherwise the process + a suitable key there. If there is, it returns the key. If there isn't, + and callout_info is not set, an error is returned. Otherwise the process proceeds to the next step. (3) request_key() sees that A doesn't have the desired key yet, so it creates @@ -62,7 +79,7 @@ A request proceeds in the following manner: instantiation. (7) The program may want to access another key from A's context (say a - Kerberos TGT key). It just requests the appropriate key, and the keyring + Kerberos TGT key). It just requests the appropriate key, and the keyring search notes that the session keyring has auth key V in its bottom level. This will permit it to then search the keyrings of process A with the @@ -79,10 +96,11 @@ A request proceeds in the following manner: (10) The program then exits 0 and request_key() deletes key V and returns key U to the caller. -This also extends further. If key W (step 7 above) didn't exist, key W would be -created uninstantiated, another auth key (X) would be created (as per step 3) -and another copy of /sbin/request-key spawned (as per step 4); but the context -specified by auth key X will still be process A, as it was in auth key V. +This also extends further. If key W (step 7 above) didn't exist, key W would +be created uninstantiated, another auth key (X) would be created (as per step +3) and another copy of /sbin/request-key spawned (as per step 4); but the +context specified by auth key X will still be process A, as it was in auth key +V. This is because process A's keyrings can't simply be attached to /sbin/request-key at the appropriate places because (a) execve will discard two @@ -118,17 +136,17 @@ A search of any particular keyring proceeds in the following fashion: (2) It considers all the non-keyring keys within that keyring and, if any key matches the criteria specified, calls key_permission(SEARCH) on it to see - if the key is allowed to be found. If it is, that key is returned; if + if the key is allowed to be found. If it is, that key is returned; if not, the search continues, and the error code is retained if of higher priority than the one currently set. (3) It then considers all the keyring-type keys in the keyring it's currently - searching. It calls key_permission(SEARCH) on each keyring, and if this + searching. It calls key_permission(SEARCH) on each keyring, and if this grants permission, it recurses, executing steps (2) and (3) on that keyring. The process stops immediately a valid key is found with permission granted to -use it. Any error from a previous match attempt is discarded and the key is +use it. Any error from a previous match attempt is discarded and the key is returned. When search_process_keyrings() is invoked, it performs the following searches @@ -153,7 +171,7 @@ The moment one succeeds, all pending errors are discarded and the found key is returned. Only if all these fail does the whole thing fail with the highest priority -error. Note that several errors may have come from LSM. +error. Note that several errors may have come from LSM. The error priority is: diff --git a/Documentation/keys.txt b/Documentation/keys.txt index 61c0fad2fe2f..e373f0212843 100644 --- a/Documentation/keys.txt +++ b/Documentation/keys.txt @@ -780,6 +780,17 @@ payload contents" for more information. See also Documentation/keys-request-key.txt. +(*) To search for a key, passing auxiliary data to the upcaller, call: + + struct key *request_key_with_auxdata(const struct key_type *type, + const char *description, + const char *callout_string, + void *aux); + + This is identical to request_key(), except that the auxiliary data is + passed to the key_type->request_key() op if it exists. + + (*) When it is no longer required, the key should be released using: void key_put(struct key *key); @@ -1031,6 +1042,24 @@ The structure has a number of fields, some of which are mandatory: as might happen when the userspace buffer is accessed. + (*) int (*request_key)(struct key *key, struct key *authkey, const char *op, + void *aux); + + This method is optional. If provided, request_key() and + request_key_with_auxdata() will invoke this function rather than + upcalling to /sbin/request-key to operate upon a key of this type. + + The aux parameter is as passed to request_key_with_auxdata() or is NULL + otherwise. Also passed are the key to be operated upon, the + authorisation key for this operation and the operation type (currently + only "create"). + + This function should return only when the upcall is complete. Upon return + the authorisation key will be revoked, and the target key will be + negatively instantiated if it is still uninstantiated. The error will be + returned to the caller of request_key*(). + + ============================ REQUEST-KEY CALLBACK SERVICE ============================ diff --git a/Documentation/pi-futex.txt b/Documentation/pi-futex.txt new file mode 100644 index 000000000000..5d61dacd21f6 --- /dev/null +++ b/Documentation/pi-futex.txt @@ -0,0 +1,121 @@ +Lightweight PI-futexes +---------------------- + +We are calling them lightweight for 3 reasons: + + - in the user-space fastpath a PI-enabled futex involves no kernel work + (or any other PI complexity) at all. No registration, no extra kernel + calls - just pure fast atomic ops in userspace. + + - even in the slowpath, the system call and scheduling pattern is very + similar to normal futexes. + + - the in-kernel PI implementation is streamlined around the mutex + abstraction, with strict rules that keep the implementation + relatively simple: only a single owner may own a lock (i.e. no + read-write lock support), only the owner may unlock a lock, no + recursive locking, etc. + +Priority Inheritance - why? +--------------------------- + +The short reply: user-space PI helps achieving/improving determinism for +user-space applications. In the best-case, it can help achieve +determinism and well-bound latencies. Even in the worst-case, PI will +improve the statistical distribution of locking related application +delays. + +The longer reply: +----------------- + +Firstly, sharing locks between multiple tasks is a common programming +technique that often cannot be replaced with lockless algorithms. As we +can see it in the kernel [which is a quite complex program in itself], +lockless structures are rather the exception than the norm - the current +ratio of lockless vs. locky code for shared data structures is somewhere +between 1:10 and 1:100. Lockless is hard, and the complexity of lockless +algorithms often endangers to ability to do robust reviews of said code. +I.e. critical RT apps often choose lock structures to protect critical +data structures, instead of lockless algorithms. Furthermore, there are +cases (like shared hardware, or other resource limits) where lockless +access is mathematically impossible. + +Media players (such as Jack) are an example of reasonable application +design with multiple tasks (with multiple priority levels) sharing +short-held locks: for example, a highprio audio playback thread is +combined with medium-prio construct-audio-data threads and low-prio +display-colory-stuff threads. Add video and decoding to the mix and +we've got even more priority levels. + +So once we accept that synchronization objects (locks) are an +unavoidable fact of life, and once we accept that multi-task userspace +apps have a very fair expectation of being able to use locks, we've got +to think about how to offer the option of a deterministic locking +implementation to user-space. + +Most of the technical counter-arguments against doing priority +inheritance only apply to kernel-space locks. But user-space locks are +different, there we cannot disable interrupts or make the task +non-preemptible in a critical section, so the 'use spinlocks' argument +does not apply (user-space spinlocks have the same priority inversion +problems as other user-space locking constructs). Fact is, pretty much +the only technique that currently enables good determinism for userspace +locks (such as futex-based pthread mutexes) is priority inheritance: + +Currently (without PI), if a high-prio and a low-prio task shares a lock +[this is a quite common scenario for most non-trivial RT applications], +even if all critical sections are coded carefully to be deterministic +(i.e. all critical sections are short in duration and only execute a +limited number of instructions), the kernel cannot guarantee any +deterministic execution of the high-prio task: any medium-priority task +could preempt the low-prio task while it holds the shared lock and +executes the critical section, and could delay it indefinitely. + +Implementation: +--------------- + +As mentioned before, the userspace fastpath of PI-enabled pthread +mutexes involves no kernel work at all - they behave quite similarly to +normal futex-based locks: a 0 value means unlocked, and a value==TID +means locked. (This is the same method as used by list-based robust +futexes.) Userspace uses atomic ops to lock/unlock these mutexes without +entering the kernel. + +To handle the slowpath, we have added two new futex ops: + + FUTEX_LOCK_PI + FUTEX_UNLOCK_PI + +If the lock-acquire fastpath fails, [i.e. an atomic transition from 0 to +TID fails], then FUTEX_LOCK_PI is called. The kernel does all the +remaining work: if there is no futex-queue attached to the futex address +yet then the code looks up the task that owns the futex [it has put its +own TID into the futex value], and attaches a 'PI state' structure to +the futex-queue. The pi_state includes an rt-mutex, which is a PI-aware, +kernel-based synchronization object. The 'other' task is made the owner +of the rt-mutex, and the FUTEX_WAITERS bit is atomically set in the +futex value. Then this task tries to lock the rt-mutex, on which it +blocks. Once it returns, it has the mutex acquired, and it sets the +futex value to its own TID and returns. Userspace has no other work to +perform - it now owns the lock, and futex value contains +FUTEX_WAITERS|TID. + +If the unlock side fastpath succeeds, [i.e. userspace manages to do a +TID -> 0 atomic transition of the futex value], then no kernel work is +triggered. + +If the unlock fastpath fails (because the FUTEX_WAITERS bit is set), +then FUTEX_UNLOCK_PI is called, and the kernel unlocks the futex on the +behalf of userspace - and it also unlocks the attached +pi_state->rt_mutex and thus wakes up any potential waiters. + +Note that under this approach, contrary to previous PI-futex approaches, +there is no prior 'registration' of a PI-futex. [which is not quite +possible anyway, due to existing ABI properties of pthread mutexes.] + +Also, under this scheme, 'robustness' and 'PI' are two orthogonal +properties of futexes, and all four combinations are possible: futex, +robust-futex, PI-futex, robust+PI-futex. + +More details about priority inheritance can be found in +Documentation/rtmutex.txt. diff --git a/Documentation/robust-futexes.txt b/Documentation/robust-futexes.txt index df82d75245a0..76e8064b8c3a 100644 --- a/Documentation/robust-futexes.txt +++ b/Documentation/robust-futexes.txt @@ -95,7 +95,7 @@ comparison. If the thread has registered a list, then normally the list is empty. If the thread/process crashed or terminated in some incorrect way then the list might be non-empty: in this case the kernel carefully walks the list [not trusting it], and marks all locks that are owned by -this thread with the FUTEX_OWNER_DEAD bit, and wakes up one waiter (if +this thread with the FUTEX_OWNER_DIED bit, and wakes up one waiter (if any). The list is guaranteed to be private and per-thread at do_exit() time, diff --git a/Documentation/rt-mutex-design.txt b/Documentation/rt-mutex-design.txt new file mode 100644 index 000000000000..c472ffacc2f6 --- /dev/null +++ b/Documentation/rt-mutex-design.txt @@ -0,0 +1,781 @@ +# +# Copyright (c) 2006 Steven Rostedt +# Licensed under the GNU Free Documentation License, Version 1.2 +# + +RT-mutex implementation design +------------------------------ + +This document tries to describe the design of the rtmutex.c implementation. +It doesn't describe the reasons why rtmutex.c exists. For that please see +Documentation/rt-mutex.txt. Although this document does explain problems +that happen without this code, but that is in the concept to understand +what the code actually is doing. + +The goal of this document is to help others understand the priority +inheritance (PI) algorithm that is used, as well as reasons for the +decisions that were made to implement PI in the manner that was done. + + +Unbounded Priority Inversion +---------------------------- + +Priority inversion is when a lower priority process executes while a higher +priority process wants to run. This happens for several reasons, and +most of the time it can't be helped. Anytime a high priority process wants +to use a resource that a lower priority process has (a mutex for example), +the high priority process must wait until the lower priority process is done +with the resource. This is a priority inversion. What we want to prevent +is something called unbounded priority inversion. That is when the high +priority process is prevented from running by a lower priority process for +an undetermined amount of time. + +The classic example of unbounded priority inversion is were you have three +processes, let's call them processes A, B, and C, where A is the highest +priority process, C is the lowest, and B is in between. A tries to grab a lock +that C owns and must wait and lets C run to release the lock. But in the +meantime, B executes, and since B is of a higher priority than C, it preempts C, +but by doing so, it is in fact preempting A which is a higher priority process. +Now there's no way of knowing how long A will be sleeping waiting for C +to release the lock, because for all we know, B is a CPU hog and will +never give C a chance to release the lock. This is called unbounded priority +inversion. + +Here's a little ASCII art to show the problem. + + grab lock L1 (owned by C) + | +A ---+ + C preempted by B + | +C +----+ + +B +--------> + B now keeps A from running. + + +Priority Inheritance (PI) +------------------------- + +There are several ways to solve this issue, but other ways are out of scope +for this document. Here we only discuss PI. + +PI is where a process inherits the priority of another process if the other +process blocks on a lock owned by the current process. To make this easier +to understand, let's use the previous example, with processes A, B, and C again. + +This time, when A blocks on the lock owned by C, C would inherit the priority +of A. So now if B becomes runnable, it would not preempt C, since C now has +the high priority of A. As soon as C releases the lock, it loses its +inherited priority, and A then can continue with the resource that C had. + +Terminology +----------- + +Here I explain some terminology that is used in this document to help describe +the design that is used to implement PI. + +PI chain - The PI chain is an ordered series of locks and processes that cause + processes to inherit priorities from a previous process that is + blocked on one of its locks. This is described in more detail + later in this document. + +mutex - In this document, to differentiate from locks that implement + PI and spin locks that are used in the PI code, from now on + the PI locks will be called a mutex. + +lock - In this document from now on, I will use the term lock when + referring to spin locks that are used to protect parts of the PI + algorithm. These locks disable preemption for UP (when + CONFIG_PREEMPT is enabled) and on SMP prevents multiple CPUs from + entering critical sections simultaneously. + +spin lock - Same as lock above. + +waiter - A waiter is a struct that is stored on the stack of a blocked + process. Since the scope of the waiter is within the code for + a process being blocked on the mutex, it is fine to allocate + the waiter on the process's stack (local variable). This + structure holds a pointer to the task, as well as the mutex that + the task is blocked on. It also has the plist node structures to + place the task in the waiter_list of a mutex as well as the + pi_list of a mutex owner task (described below). + + waiter is sometimes used in reference to the task that is waiting + on a mutex. This is the same as waiter->task. + +waiters - A list of processes that are blocked on a mutex. + +top waiter - The highest priority process waiting on a specific mutex. + +top pi waiter - The highest priority process waiting on one of the mutexes + that a specific process owns. + +Note: task and process are used interchangeably in this document, mostly to + differentiate between two processes that are being described together. + + +PI chain +-------- + +The PI chain is a list of processes and mutexes that may cause priority +inheritance to take place. Multiple chains may converge, but a chain +would never diverge, since a process can't be blocked on more than one +mutex at a time. + +Example: + + Process: A, B, C, D, E + Mutexes: L1, L2, L3, L4 + + A owns: L1 + B blocked on L1 + B owns L2 + C blocked on L2 + C owns L3 + D blocked on L3 + D owns L4 + E blocked on L4 + +The chain would be: + + E->L4->D->L3->C->L2->B->L1->A + +To show where two chains merge, we could add another process F and +another mutex L5 where B owns L5 and F is blocked on mutex L5. + +The chain for F would be: + + F->L5->B->L1->A + +Since a process may own more than one mutex, but never be blocked on more than +one, the chains merge. + +Here we show both chains: + + E->L4->D->L3->C->L2-+ + | + +->B->L1->A + | + F->L5-+ + +For PI to work, the processes at the right end of these chains (or we may +also call it the Top of the chain) must be equal to or higher in priority +than the processes to the left or below in the chain. + +Also since a mutex may have more than one process blocked on it, we can +have multiple chains merge at mutexes. If we add another process G that is +blocked on mutex L2: + + G->L2->B->L1->A + +And once again, to show how this can grow I will show the merging chains +again. + + E->L4->D->L3->C-+ + +->L2-+ + | | + G-+ +->B->L1->A + | + F->L5-+ + + +Plist +----- + +Before I go further and talk about how the PI chain is stored through lists +on both mutexes and processes, I'll explain the plist. This is similar to +the struct list_head functionality that is already in the kernel. +The implementation of plist is out of scope for this document, but it is +very important to understand what it does. + +There are a few differences between plist and list, the most important one +being that plist is a priority sorted linked list. This means that the +priorities of the plist are sorted, such that it takes O(1) to retrieve the +highest priority item in the list. Obviously this is useful to store processes +based on their priorities. + +Another difference, which is important for implementation, is that, unlike +list, the head of the list is a different element than the nodes of a list. +So the head of the list is declared as struct plist_head and nodes that will +be added to the list are declared as struct plist_node. + + +Mutex Waiter List +----------------- + +Every mutex keeps track of all the waiters that are blocked on itself. The mutex +has a plist to store these waiters by priority. This list is protected by +a spin lock that is located in the struct of the mutex. This lock is called +wait_lock. Since the modification of the waiter list is never done in +interrupt context, the wait_lock can be taken without disabling interrupts. + + +Task PI List +------------ + +To keep track of the PI chains, each process has its own PI list. This is +a list of all top waiters of the mutexes that are owned by the process. +Note that this list only holds the top waiters and not all waiters that are +blocked on mutexes owned by the process. + +The top of the task's PI list is always the highest priority task that +is waiting on a mutex that is owned by the task. So if the task has +inherited a priority, it will always be the priority of the task that is +at the top of this list. + +This list is stored in the task structure of a process as a plist called +pi_list. This list is protected by a spin lock also in the task structure, +called pi_lock. This lock may also be taken in interrupt context, so when +locking the pi_lock, interrupts must be disabled. + + +Depth of the PI Chain +--------------------- + +The maximum depth of the PI chain is not dynamic, and could actually be +defined. But is very complex to figure it out, since it depends on all +the nesting of mutexes. Let's look at the example where we have 3 mutexes, +L1, L2, and L3, and four separate functions func1, func2, func3 and func4. +The following shows a locking order of L1->L2->L3, but may not actually +be directly nested that way. + +void func1(void) +{ + mutex_lock(L1); + + /* do anything */ + + mutex_unlock(L1); +} + +void func2(void) +{ + mutex_lock(L1); + mutex_lock(L2); + + /* do something */ + + mutex_unlock(L2); + mutex_unlock(L1); +} + +void func3(void) +{ + mutex_lock(L2); + mutex_lock(L3); + + /* do something else */ + + mutex_unlock(L3); + mutex_unlock(L2); +} + +void func4(void) +{ + mutex_lock(L3); + + /* do something again */ + + mutex_unlock(L3); +} + +Now we add 4 processes that run each of these functions separately. +Processes A, B, C, and D which run functions func1, func2, func3 and func4 +respectively, and such that D runs first and A last. With D being preempted +in func4 in the "do something again" area, we have a locking that follows: + +D owns L3 + C blocked on L3 + C owns L2 + B blocked on L2 + B owns L1 + A blocked on L1 + +And thus we have the chain A->L1->B->L2->C->L3->D. + +This gives us a PI depth of 4 (four processes), but looking at any of the +functions individually, it seems as though they only have at most a locking +depth of two. So, although the locking depth is defined at compile time, +it still is very difficult to find the possibilities of that depth. + +Now since mutexes can be defined by user-land applications, we don't want a DOS +type of application that nests large amounts of mutexes to create a large +PI chain, and have the code holding spin locks while looking at a large +amount of data. So to prevent this, the implementation not only implements +a maximum lock depth, but also only holds at most two different locks at a +time, as it walks the PI chain. More about this below. + + +Mutex owner and flags +--------------------- + +The mutex structure contains a pointer to the owner of the mutex. If the +mutex is not owned, this owner is set to NULL. Since all architectures +have the task structure on at least a four byte alignment (and if this is +not true, the rtmutex.c code will be broken!), this allows for the two +least significant bits to be used as flags. This part is also described +in Documentation/rt-mutex.txt, but will also be briefly described here. + +Bit 0 is used as the "Pending Owner" flag. This is described later. +Bit 1 is used as the "Has Waiters" flags. This is also described later + in more detail, but is set whenever there are waiters on a mutex. + + +cmpxchg Tricks +-------------- + +Some architectures implement an atomic cmpxchg (Compare and Exchange). This +is used (when applicable) to keep the fast path of grabbing and releasing +mutexes short. + +cmpxchg is basically the following function performed atomically: + +unsigned long _cmpxchg(unsigned long *A, unsigned long *B, unsigned long *C) +{ + unsigned long T = *A; + if (*A == *B) { + *A = *C; + } + return T; +} +#define cmpxchg(a,b,c) _cmpxchg(&a,&b,&c) + +This is really nice to have, since it allows you to only update a variable +if the variable is what you expect it to be. You know if it succeeded if +the return value (the old value of A) is equal to B. + +The macro rt_mutex_cmpxchg is used to try to lock and unlock mutexes. If +the architecture does not support CMPXCHG, then this macro is simply set +to fail every time. But if CMPXCHG is supported, then this will +help out extremely to keep the fast path short. + +The use of rt_mutex_cmpxchg with the flags in the owner field help optimize +the system for architectures that support it. This will also be explained +later in this document. + + +Priority adjustments +-------------------- + +The implementation of the PI code in rtmutex.c has several places that a +process must adjust its priority. With the help of the pi_list of a +process this is rather easy to know what needs to be adjusted. + +The functions implementing the task adjustments are rt_mutex_adjust_prio, +__rt_mutex_adjust_prio (same as the former, but expects the task pi_lock +to already be taken), rt_mutex_get_prio, and rt_mutex_setprio. + +rt_mutex_getprio and rt_mutex_setprio are only used in __rt_mutex_adjust_prio. + +rt_mutex_getprio returns the priority that the task should have. Either the +task's own normal priority, or if a process of a higher priority is waiting on +a mutex owned by the task, then that higher priority should be returned. +Since the pi_list of a task holds an order by priority list of all the top +waiters of all the mutexes that the task owns, rt_mutex_getprio simply needs +to compare the top pi waiter to its own normal priority, and return the higher +priority back. + +(Note: if looking at the code, you will notice that the lower number of + prio is returned. This is because the prio field in the task structure + is an inverse order of the actual priority. So a "prio" of 5 is + of higher priority than a "prio" of 10.) + +__rt_mutex_adjust_prio examines the result of rt_mutex_getprio, and if the +result does not equal the task's current priority, then rt_mutex_setprio +is called to adjust the priority of the task to the new priority. +Note that rt_mutex_setprio is defined in kernel/sched.c to implement the +actual change in priority. + +It is interesting to note that __rt_mutex_adjust_prio can either increase +or decrease the priority of the task. In the case that a higher priority +process has just blocked on a mutex owned by the task, __rt_mutex_adjust_prio +would increase/boost the task's priority. But if a higher priority task +were for some reason to leave the mutex (timeout or signal), this same function +would decrease/unboost the priority of the task. That is because the pi_list +always contains the highest priority task that is waiting on a mutex owned +by the task, so we only need to compare the priority of that top pi waiter +to the normal priority of the given task. + + +High level overview of the PI chain walk +---------------------------------------- + +The PI chain walk is implemented by the function rt_mutex_adjust_prio_chain. + +The implementation has gone through several iterations, and has ended up +with what we believe is the best. It walks the PI chain by only grabbing +at most two locks at a time, and is very efficient. + +The rt_mutex_adjust_prio_chain can be used either to boost or lower process +priorities. + +rt_mutex_adjust_prio_chain is called with a task to be checked for PI +(de)boosting (the owner of a mutex that a process is blocking on), a flag to +check for deadlocking, the mutex that the task owns, and a pointer to a waiter +that is the process's waiter struct that is blocked on the mutex (although this +parameter may be NULL for deboosting). + +For this explanation, I will not mention deadlock detection. This explanation +will try to stay at a high level. + +When this function is called, there are no locks held. That also means +that the state of the owner and lock can change when entered into this function. + +Before this function is called, the task has already had rt_mutex_adjust_prio +performed on it. This means that the task is set to the priority that it +should be at, but the plist nodes of the task's waiter have not been updated +with the new priorities, and that this task may not be in the proper locations +in the pi_lists and wait_lists that the task is blocked on. This function +solves all that. + +A loop is entered, where task is the owner to be checked for PI changes that +was passed by parameter (for the first iteration). The pi_lock of this task is +taken to prevent any more changes to the pi_list of the task. This also +prevents new tasks from completing the blocking on a mutex that is owned by this +task. + +If the task is not blocked on a mutex then the loop is exited. We are at +the top of the PI chain. + +A check is now done to see if the original waiter (the process that is blocked +on the current mutex) is the top pi waiter of the task. That is, is this +waiter on the top of the task's pi_list. If it is not, it either means that +there is another process higher in priority that is blocked on one of the +mutexes that the task owns, or that the waiter has just woken up via a signal +or timeout and has left the PI chain. In either case, the loop is exited, since +we don't need to do any more changes to the priority of the current task, or any +task that owns a mutex that this current task is waiting on. A priority chain +walk is only needed when a new top pi waiter is made to a task. + +The next check sees if the task's waiter plist node has the priority equal to +the priority the task is set at. If they are equal, then we are done with +the loop. Remember that the function started with the priority of the +task adjusted, but the plist nodes that hold the task in other processes +pi_lists have not been adjusted. + +Next, we look at the mutex that the task is blocked on. The mutex's wait_lock +is taken. This is done by a spin_trylock, because the locking order of the +pi_lock and wait_lock goes in the opposite direction. If we fail to grab the +lock, the pi_lock is released, and we restart the loop. + +Now that we have both the pi_lock of the task as well as the wait_lock of +the mutex the task is blocked on, we update the task's waiter's plist node +that is located on the mutex's wait_list. + +Now we release the pi_lock of the task. + +Next the owner of the mutex has its pi_lock taken, so we can update the +task's entry in the owner's pi_list. If the task is the highest priority +process on the mutex's wait_list, then we remove the previous top waiter +from the owner's pi_list, and replace it with the task. + +Note: It is possible that the task was the current top waiter on the mutex, + in which case the task is not yet on the pi_list of the waiter. This + is OK, since plist_del does nothing if the plist node is not on any + list. + +If the task was not the top waiter of the mutex, but it was before we +did the priority updates, that means we are deboosting/lowering the +task. In this case, the task is removed from the pi_list of the owner, +and the new top waiter is added. + +Lastly, we unlock both the pi_lock of the task, as well as the mutex's +wait_lock, and continue the loop again. On the next iteration of the +loop, the previous owner of the mutex will be the task that will be +processed. + +Note: One might think that the owner of this mutex might have changed + since we just grab the mutex's wait_lock. And one could be right. + The important thing to remember is that the owner could not have + become the task that is being processed in the PI chain, since + we have taken that task's pi_lock at the beginning of the loop. + So as long as there is an owner of this mutex that is not the same + process as the tasked being worked on, we are OK. + + Looking closely at the code, one might be confused. The check for the + end of the PI chain is when the task isn't blocked on anything or the + task's waiter structure "task" element is NULL. This check is + protected only by the task's pi_lock. But the code to unlock the mutex + sets the task's waiter structure "task" element to NULL with only + the protection of the mutex's wait_lock, which was not taken yet. + Isn't this a race condition if the task becomes the new owner? + + The answer is No! The trick is the spin_trylock of the mutex's + wait_lock. If we fail that lock, we release the pi_lock of the + task and continue the loop, doing the end of PI chain check again. + + In the code to release the lock, the wait_lock of the mutex is held + the entire time, and it is not let go when we grab the pi_lock of the + new owner of the mutex. So if the switch of a new owner were to happen + after the check for end of the PI chain and the grabbing of the + wait_lock, the unlocking code would spin on the new owner's pi_lock + but never give up the wait_lock. So the PI chain loop is guaranteed to + fail the spin_trylock on the wait_lock, release the pi_lock, and + try again. + + If you don't quite understand the above, that's OK. You don't have to, + unless you really want to make a proof out of it ;) + + +Pending Owners and Lock stealing +-------------------------------- + +One of the flags in the owner field of the mutex structure is "Pending Owner". +What this means is that an owner was chosen by the process releasing the +mutex, but that owner has yet to wake up and actually take the mutex. + +Why is this important? Why can't we just give the mutex to another process +and be done with it? + +The PI code is to help with real-time processes, and to let the highest +priority process run as long as possible with little latencies and delays. +If a high priority process owns a mutex that a lower priority process is +blocked on, when the mutex is released it would be given to the lower priority +process. What if the higher priority process wants to take that mutex again. +The high priority process would fail to take that mutex that it just gave up +and it would need to boost the lower priority process to run with full +latency of that critical section (since the low priority process just entered +it). + +There's no reason a high priority process that gives up a mutex should be +penalized if it tries to take that mutex again. If the new owner of the +mutex has not woken up yet, there's no reason that the higher priority process +could not take that mutex away. + +To solve this, we introduced Pending Ownership and Lock Stealing. When a +new process is given a mutex that it was blocked on, it is only given +pending ownership. This means that it's the new owner, unless a higher +priority process comes in and tries to grab that mutex. If a higher priority +process does come along and wants that mutex, we let the higher priority +process "steal" the mutex from the pending owner (only if it is still pending) +and continue with the mutex. + + +Taking of a mutex (The walk through) +------------------------------------ + +OK, now let's take a look at the detailed walk through of what happens when +taking a mutex. + +The first thing that is tried is the fast taking of the mutex. This is +done when we have CMPXCHG enabled (otherwise the fast taking automatically +fails). Only when the owner field of the mutex is NULL can the lock be +taken with the CMPXCHG and nothing else needs to be done. + +If there is contention on the lock, whether it is owned or pending owner +we go about the slow path (rt_mutex_slowlock). + +The slow path function is where the task's waiter structure is created on +the stack. This is because the waiter structure is only needed for the +scope of this function. The waiter structure holds the nodes to store +the task on the wait_list of the mutex, and if need be, the pi_list of +the owner. + +The wait_lock of the mutex is taken since the slow path of unlocking the +mutex also takes this lock. + +We then call try_to_take_rt_mutex. This is where the architecture that +does not implement CMPXCHG would always grab the lock (if there's no +contention). + +try_to_take_rt_mutex is used every time the task tries to grab a mutex in the +slow path. The first thing that is done here is an atomic setting of +the "Has Waiters" flag of the mutex's owner field. Yes, this could really +be false, because if the the mutex has no owner, there are no waiters and +the current task also won't have any waiters. But we don't have the lock +yet, so we assume we are going to be a waiter. The reason for this is to +play nice for those architectures that do have CMPXCHG. By setting this flag +now, the owner of the mutex can't release the mutex without going into the +slow unlock path, and it would then need to grab the wait_lock, which this +code currently holds. So setting the "Has Waiters" flag forces the owner +to synchronize with this code. + +Now that we know that we can't have any races with the owner releasing the +mutex, we check to see if we can take the ownership. This is done if the +mutex doesn't have a owner, or if we can steal the mutex from a pending +owner. Let's look at the situations we have here. + + 1) Has owner that is pending + ---------------------------- + + The mutex has a owner, but it hasn't woken up and the mutex flag + "Pending Owner" is set. The first check is to see if the owner isn't the + current task. This is because this function is also used for the pending + owner to grab the mutex. When a pending owner wakes up, it checks to see + if it can take the mutex, and this is done if the owner is already set to + itself. If so, we succeed and leave the function, clearing the "Pending + Owner" bit. + + If the pending owner is not current, we check to see if the current priority is + higher than the pending owner. If not, we fail the function and return. + + There's also something special about a pending owner. That is a pending owner + is never blocked on a mutex. So there is no PI chain to worry about. It also + means that if the mutex doesn't have any waiters, there's no accounting needed + to update the pending owner's pi_list, since we only worry about processes + blocked on the current mutex. + + If there are waiters on this mutex, and we just stole the ownership, we need + to take the top waiter, remove it from the pi_list of the pending owner, and + add it to the current pi_list. Note that at this moment, the pending owner + is no longer on the list of waiters. This is fine, since the pending owner + would add itself back when it realizes that it had the ownership stolen + from itself. When the pending owner tries to grab the mutex, it will fail + in try_to_take_rt_mutex if the owner field points to another process. + + 2) No owner + ----------- + + If there is no owner (or we successfully stole the lock), we set the owner + of the mutex to current, and set the flag of "Has Waiters" if the current + mutex actually has waiters, or we clear the flag if it doesn't. See, it was + OK that we set that flag early, since now it is cleared. + + 3) Failed to grab ownership + --------------------------- + + The most interesting case is when we fail to take ownership. This means that + there exists an owner, or there's a pending owner with equal or higher + priority than the current task. + +We'll continue on the failed case. + +If the mutex has a timeout, we set up a timer to go off to break us out +of this mutex if we failed to get it after a specified amount of time. + +Now we enter a loop that will continue to try to take ownership of the mutex, or +fail from a timeout or signal. + +Once again we try to take the mutex. This will usually fail the first time +in the loop, since it had just failed to get the mutex. But the second time +in the loop, this would likely succeed, since the task would likely be +the pending owner. + +If the mutex is TASK_INTERRUPTIBLE a check for signals and timeout is done +here. + +The waiter structure has a "task" field that points to the task that is blocked +on the mutex. This field can be NULL the first time it goes through the loop +or if the task is a pending owner and had it's mutex stolen. If the "task" +field is NULL then we need to set up the accounting for it. + +Task blocks on mutex +-------------------- + +The accounting of a mutex and process is done with the waiter structure of +the process. The "task" field is set to the process, and the "lock" field +to the mutex. The plist nodes are initialized to the processes current +priority. + +Since the wait_lock was taken at the entry of the slow lock, we can safely +add the waiter to the wait_list. If the current process is the highest +priority process currently waiting on this mutex, then we remove the +previous top waiter process (if it exists) from the pi_list of the owner, +and add the current process to that list. Since the pi_list of the owner +has changed, we call rt_mutex_adjust_prio on the owner to see if the owner +should adjust its priority accordingly. + +If the owner is also blocked on a lock, and had its pi_list changed +(or deadlock checking is on), we unlock the wait_lock of the mutex and go ahead +and run rt_mutex_adjust_prio_chain on the owner, as described earlier. + +Now all locks are released, and if the current process is still blocked on a +mutex (waiter "task" field is not NULL), then we go to sleep (call schedule). + +Waking up in the loop +--------------------- + +The schedule can then wake up for a few reasons. + 1) we were given pending ownership of the mutex. + 2) we received a signal and was TASK_INTERRUPTIBLE + 3) we had a timeout and was TASK_INTERRUPTIBLE + +In any of these cases, we continue the loop and once again try to grab the +ownership of the mutex. If we succeed, we exit the loop, otherwise we continue +and on signal and timeout, will exit the loop, or if we had the mutex stolen +we just simply add ourselves back on the lists and go back to sleep. + +Note: For various reasons, because of timeout and signals, the steal mutex + algorithm needs to be careful. This is because the current process is + still on the wait_list. And because of dynamic changing of priorities, + especially on SCHED_OTHER tasks, the current process can be the + highest priority task on the wait_list. + +Failed to get mutex on Timeout or Signal +---------------------------------------- + +If a timeout or signal occurred, the waiter's "task" field would not be +NULL and the task needs to be taken off the wait_list of the mutex and perhaps +pi_list of the owner. If this process was a high priority process, then +the rt_mutex_adjust_prio_chain needs to be executed again on the owner, +but this time it will be lowering the priorities. + + +Unlocking the Mutex +------------------- + +The unlocking of a mutex also has a fast path for those architectures with +CMPXCHG. Since the taking of a mutex on contention always sets the +"Has Waiters" flag of the mutex's owner, we use this to know if we need to +take the slow path when unlocking the mutex. If the mutex doesn't have any +waiters, the owner field of the mutex would equal the current process and +the mutex can be unlocked by just replacing the owner field with NULL. + +If the owner field has the "Has Waiters" bit set (or CMPXCHG is not available), +the slow unlock path is taken. + +The first thing done in the slow unlock path is to take the wait_lock of the +mutex. This synchronizes the locking and unlocking of the mutex. + +A check is made to see if the mutex has waiters or not. On architectures that +do not have CMPXCHG, this is the location that the owner of the mutex will +determine if a waiter needs to be awoken or not. On architectures that +do have CMPXCHG, that check is done in the fast path, but it is still needed +in the slow path too. If a waiter of a mutex woke up because of a signal +or timeout between the time the owner failed the fast path CMPXCHG check and +the grabbing of the wait_lock, the mutex may not have any waiters, thus the +owner still needs to make this check. If there are no waiters than the mutex +owner field is set to NULL, the wait_lock is released and nothing more is +needed. + +If there are waiters, then we need to wake one up and give that waiter +pending ownership. + +On the wake up code, the pi_lock of the current owner is taken. The top +waiter of the lock is found and removed from the wait_list of the mutex +as well as the pi_list of the current owner. The task field of the new +pending owner's waiter structure is set to NULL, and the owner field of the +mutex is set to the new owner with the "Pending Owner" bit set, as well +as the "Has Waiters" bit if there still are other processes blocked on the +mutex. + +The pi_lock of the previous owner is released, and the new pending owner's +pi_lock is taken. Remember that this is the trick to prevent the race +condition in rt_mutex_adjust_prio_chain from adding itself as a waiter +on the mutex. + +We now clear the "pi_blocked_on" field of the new pending owner, and if +the mutex still has waiters pending, we add the new top waiter to the pi_list +of the pending owner. + +Finally we unlock the pi_lock of the pending owner and wake it up. + + +Contact +------- + +For updates on this document, please email Steven Rostedt <rostedt@goodmis.org> + + +Credits +------- + +Author: Steven Rostedt <rostedt@goodmis.org> + +Reviewers: Ingo Molnar, Thomas Gleixner, Thomas Duetsch, and Randy Dunlap + +Updates +------- + +This document was originally written for 2.6.17-rc3-mm1 diff --git a/Documentation/rt-mutex.txt b/Documentation/rt-mutex.txt new file mode 100644 index 000000000000..243393d882ee --- /dev/null +++ b/Documentation/rt-mutex.txt @@ -0,0 +1,79 @@ +RT-mutex subsystem with PI support +---------------------------------- + +RT-mutexes with priority inheritance are used to support PI-futexes, +which enable pthread_mutex_t priority inheritance attributes +(PTHREAD_PRIO_INHERIT). [See Documentation/pi-futex.txt for more details +about PI-futexes.] + +This technology was developed in the -rt tree and streamlined for +pthread_mutex support. + +Basic principles: +----------------- + +RT-mutexes extend the semantics of simple mutexes by the priority +inheritance protocol. + +A low priority owner of a rt-mutex inherits the priority of a higher +priority waiter until the rt-mutex is released. If the temporarily +boosted owner blocks on a rt-mutex itself it propagates the priority +boosting to the owner of the other rt_mutex it gets blocked on. The +priority boosting is immediately removed once the rt_mutex has been +unlocked. + +This approach allows us to shorten the block of high-prio tasks on +mutexes which protect shared resources. Priority inheritance is not a +magic bullet for poorly designed applications, but it allows +well-designed applications to use userspace locks in critical parts of +an high priority thread, without losing determinism. + +The enqueueing of the waiters into the rtmutex waiter list is done in +priority order. For same priorities FIFO order is chosen. For each +rtmutex, only the top priority waiter is enqueued into the owner's +priority waiters list. This list too queues in priority order. Whenever +the top priority waiter of a task changes (for example it timed out or +got a signal), the priority of the owner task is readjusted. [The +priority enqueueing is handled by "plists", see include/linux/plist.h +for more details.] + +RT-mutexes are optimized for fastpath operations and have no internal +locking overhead when locking an uncontended mutex or unlocking a mutex +without waiters. The optimized fastpath operations require cmpxchg +support. [If that is not available then the rt-mutex internal spinlock +is used] + +The state of the rt-mutex is tracked via the owner field of the rt-mutex +structure: + +rt_mutex->owner holds the task_struct pointer of the owner. Bit 0 and 1 +are used to keep track of the "owner is pending" and "rtmutex has +waiters" state. + + owner bit1 bit0 + NULL 0 0 mutex is free (fast acquire possible) + NULL 0 1 invalid state + NULL 1 0 Transitional state* + NULL 1 1 invalid state + taskpointer 0 0 mutex is held (fast release possible) + taskpointer 0 1 task is pending owner + taskpointer 1 0 mutex is held and has waiters + taskpointer 1 1 task is pending owner and mutex has waiters + +Pending-ownership handling is a performance optimization: +pending-ownership is assigned to the first (highest priority) waiter of +the mutex, when the mutex is released. The thread is woken up and once +it starts executing it can acquire the mutex. Until the mutex is taken +by it (bit 0 is cleared) a competing higher priority thread can "steal" +the mutex which puts the woken up thread back on the waiters list. + +The pending-ownership optimization is especially important for the +uninterrupted workflow of high-prio tasks which repeatedly +takes/releases locks that have lower-prio waiters. Without this +optimization the higher-prio thread would ping-pong to the lower-prio +task [because at unlock time we always assign a new owner]. + +(*) The "mutex has waiters" bit gets set to take the lock. If the lock +doesn't already have an owner, this bit is quickly cleared if there are +no waiters. So this is a transitional state to synchronize with looking +at the owner field of the mutex and the mutex owner releasing the lock. diff --git a/Documentation/scsi/ppa.txt b/Documentation/scsi/ppa.txt index 0dac88d86d87..5d9223bc1bd5 100644 --- a/Documentation/scsi/ppa.txt +++ b/Documentation/scsi/ppa.txt @@ -12,5 +12,3 @@ http://www.torque.net/parport/ Email list for Linux Parport linux-parport@torque.net -Email for problems with ZIP or ZIP Plus drivers -campbell@torque.net diff --git a/Documentation/sound/alsa/ALSA-Configuration.txt b/Documentation/sound/alsa/ALSA-Configuration.txt index 87d76a5c73d0..f61af23dd85d 100644 --- a/Documentation/sound/alsa/ALSA-Configuration.txt +++ b/Documentation/sound/alsa/ALSA-Configuration.txt @@ -472,6 +472,22 @@ Prior to version 0.9.0rc4 options had a 'snd_' prefix. This was removed. The power-management is supported. + Module snd-darla20 + ------------------ + + Module for Echoaudio Darla20 + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + + Module snd-darla24 + ------------------ + + Module for Echoaudio Darla24 + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + Module snd-dt019x ----------------- @@ -499,6 +515,14 @@ Prior to version 0.9.0rc4 options had a 'snd_' prefix. This was removed. The power-management is supported. + Module snd-echo3g + ----------------- + + Module for Echoaudio 3G cards (Gina3G/Layla3G) + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + Module snd-emu10k1 ------------------ @@ -657,6 +681,22 @@ Prior to version 0.9.0rc4 options had a 'snd_' prefix. This was removed. The power-management is supported. + Module snd-gina20 + ----------------- + + Module for Echoaudio Gina20 + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + + Module snd-gina24 + ----------------- + + Module for Echoaudio Gina24 + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + Module snd-gusclassic --------------------- @@ -760,12 +800,18 @@ Prior to version 0.9.0rc4 options had a 'snd_' prefix. This was removed. basic fixed pin assignment w/o SPDIF auto auto-config reading BIOS (default) - ALC882/883/885 + ALC882/885 3stack-dig 3-jack with SPDIF I/O 6stck-dig 6-jack digital with SPDIF I/O auto auto-config reading BIOS (default) - ALC861 + ALC883/888 + 3stack-dig 3-jack with SPDIF I/O + 6stack-dig 6-jack digital with SPDIF I/O + 6stack-dig-demo 6-stack digital for Intel demo board + auto auto-config reading BIOS (default) + + ALC861/660 3stack 3-jack 3stack-dig 3-jack with SPDIF I/O 6stack-dig 6-jack with SPDIF I/O @@ -937,6 +983,30 @@ Prior to version 0.9.0rc4 options had a 'snd_' prefix. This was removed. driver isn't configured properly or you want to try another type for testing. + Module snd-indigo + ----------------- + + Module for Echoaudio Indigo + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + + Module snd-indigodj + ------------------- + + Module for Echoaudio Indigo DJ + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + + Module snd-indigoio + ------------------- + + Module for Echoaudio Indigo IO + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + Module snd-intel8x0 ------------------- @@ -1036,6 +1106,22 @@ Prior to version 0.9.0rc4 options had a 'snd_' prefix. This was removed. This module supports multiple cards. + Module snd-layla20 + ------------------ + + Module for Echoaudio Layla20 + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + + Module snd-layla24 + ------------------ + + Module for Echoaudio Layla24 + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + Module snd-maestro3 ------------------- @@ -1056,6 +1142,14 @@ Prior to version 0.9.0rc4 options had a 'snd_' prefix. This was removed. The power-management is supported. + Module snd-mia + --------------- + + Module for Echoaudio Mia + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + Module snd-miro --------------- @@ -1088,6 +1182,14 @@ Prior to version 0.9.0rc4 options had a 'snd_' prefix. This was removed. When no hotplug fw loader is available, you need to load the firmware via mixartloader utility in alsa-tools package. + Module snd-mona + --------------- + + Module for Echoaudio Mona + + This module supports multiple cards. + The driver requires the firmware loader support on kernel. + Module snd-mpu401 ----------------- diff --git a/Documentation/video4linux/README.pvrusb2 b/Documentation/video4linux/README.pvrusb2 new file mode 100644 index 000000000000..c73a32c34528 --- /dev/null +++ b/Documentation/video4linux/README.pvrusb2 @@ -0,0 +1,212 @@ + +$Id$ +Mike Isely <isely@pobox.com> + + pvrusb2 driver + +Background: + + This driver is intended for the "Hauppauge WinTV PVR USB 2.0", which + is a USB 2.0 hosted TV Tuner. This driver is a work in progress. + Its history started with the reverse-engineering effort by Björn + Danielsson <pvrusb2@dax.nu> whose web page can be found here: + + http://pvrusb2.dax.nu/ + + From there Aurelien Alleaume <slts@free.fr> began an effort to + create a video4linux compatible driver. I began with Aurelien's + last known snapshot and evolved the driver to the state it is in + here. + + More information on this driver can be found at: + + http://www.isely.net/pvrusb2.html + + + This driver has a strong separation of layers. They are very + roughly: + + 1a. Low level wire-protocol implementation with the device. + + 1b. I2C adaptor implementation and corresponding I2C client drivers + implemented elsewhere in V4L. + + 1c. High level hardware driver implementation which coordinates all + activities that ensure correct operation of the device. + + 2. A "context" layer which manages instancing of driver, setup, + tear-down, arbitration, and interaction with high level + interfaces appropriately as devices are hotplugged in the + system. + + 3. High level interfaces which glue the driver to various published + Linux APIs (V4L, sysfs, maybe DVB in the future). + + The most important shearing layer is between the top 2 layers. A + lot of work went into the driver to ensure that any kind of + conceivable API can be laid on top of the core driver. (Yes, the + driver internally leverages V4L to do its work but that really has + nothing to do with the API published by the driver to the outside + world.) The architecture allows for different APIs to + simultaneously access the driver. I have a strong sense of fairness + about APIs and also feel that it is a good design principle to keep + implementation and interface isolated from each other. Thus while + right now the V4L high level interface is the most complete, the + sysfs high level interface will work equally well for similar + functions, and there's no reason I see right now why it shouldn't be + possible to produce a DVB high level interface that can sit right + alongside V4L. + + NOTE: Complete documentation on the pvrusb2 driver is contained in + the html files within the doc directory; these are exactly the same + as what is on the web site at the time. Browse those files + (especially the FAQ) before asking questions. + + +Building + + To build these modules essentially amounts to just running "Make", + but you need the kernel source tree nearby and you will likely also + want to set a few controlling environment variables first in order + to link things up with that source tree. Please see the Makefile + here for comments that explain how to do that. + + +Source file list / functional overview: + + (Note: The term "module" used below generally refers to loosely + defined functional units within the pvrusb2 driver and bears no + relation to the Linux kernel's concept of a loadable module.) + + pvrusb2-audio.[ch] - This is glue logic that resides between this + driver and the msp3400.ko I2C client driver (which is found + elsewhere in V4L). + + pvrusb2-context.[ch] - This module implements the context for an + instance of the driver. Everything else eventually ties back to + or is otherwise instanced within the data structures implemented + here. Hotplugging is ultimately coordinated here. All high level + interfaces tie into the driver through this module. This module + helps arbitrate each interface's access to the actual driver core, + and is designed to allow concurrent access through multiple + instances of multiple interfaces (thus you can for example change + the tuner's frequency through sysfs while simultaneously streaming + video through V4L out to an instance of mplayer). + + pvrusb2-debug.h - This header defines a printk() wrapper and a mask + of debugging bit definitions for the various kinds of debug + messages that can be enabled within the driver. + + pvrusb2-debugifc.[ch] - This module implements a crude command line + oriented debug interface into the driver. Aside from being part + of the process for implementing manual firmware extraction (see + the pvrusb2 web site mentioned earlier), probably I'm the only one + who has ever used this. It is mainly a debugging aid. + + pvrusb2-eeprom.[ch] - This is glue logic that resides between this + driver the tveeprom.ko module, which is itself implemented + elsewhere in V4L. + + pvrusb2-encoder.[ch] - This module implements all protocol needed to + interact with the Conexant mpeg2 encoder chip within the pvrusb2 + device. It is a crude echo of corresponding logic in ivtv, + however the design goals (strict isolation) and physical layer + (proxy through USB instead of PCI) are enough different that this + implementation had to be completely different. + + pvrusb2-hdw-internal.h - This header defines the core data structure + in the driver used to track ALL internal state related to control + of the hardware. Nobody outside of the core hardware-handling + modules should have any business using this header. All external + access to the driver should be through one of the high level + interfaces (e.g. V4L, sysfs, etc), and in fact even those high + level interfaces are restricted to the API defined in + pvrusb2-hdw.h and NOT this header. + + pvrusb2-hdw.h - This header defines the full internal API for + controlling the hardware. High level interfaces (e.g. V4L, sysfs) + will work through here. + + pvrusb2-hdw.c - This module implements all the various bits of logic + that handle overall control of a specific pvrusb2 device. + (Policy, instantiation, and arbitration of pvrusb2 devices fall + within the jurisdiction of pvrusb-context not here). + + pvrusb2-i2c-chips-*.c - These modules implement the glue logic to + tie together and configure various I2C modules as they attach to + the I2C bus. There are two versions of this file. The "v4l2" + version is intended to be used in-tree alongside V4L, where we + implement just the logic that makes sense for a pure V4L + environment. The "all" version is intended for use outside of + V4L, where we might encounter other possibly "challenging" modules + from ivtv or older kernel snapshots (or even the support modules + in the standalone snapshot). + + pvrusb2-i2c-cmd-v4l1.[ch] - This module implements generic V4L1 + compatible commands to the I2C modules. It is here where state + changes inside the pvrusb2 driver are translated into V4L1 + commands that are in turn send to the various I2C modules. + + pvrusb2-i2c-cmd-v4l2.[ch] - This module implements generic V4L2 + compatible commands to the I2C modules. It is here where state + changes inside the pvrusb2 driver are translated into V4L2 + commands that are in turn send to the various I2C modules. + + pvrusb2-i2c-core.[ch] - This module provides an implementation of a + kernel-friendly I2C adaptor driver, through which other external + I2C client drivers (e.g. msp3400, tuner, lirc) may connect and + operate corresponding chips within the the pvrusb2 device. It is + through here that other V4L modules can reach into this driver to + operate specific pieces (and those modules are in turn driven by + glue logic which is coordinated by pvrusb2-hdw, doled out by + pvrusb2-context, and then ultimately made available to users + through one of the high level interfaces). + + pvrusb2-io.[ch] - This module implements a very low level ring of + transfer buffers, required in order to stream data from the + device. This module is *very* low level. It only operates the + buffers and makes no attempt to define any policy or mechanism for + how such buffers might be used. + + pvrusb2-ioread.[ch] - This module layers on top of pvrusb2-io.[ch] + to provide a streaming API usable by a read() system call style of + I/O. Right now this is the only layer on top of pvrusb2-io.[ch], + however the underlying architecture here was intended to allow for + other styles of I/O to be implemented with additonal modules, like + mmap()'ed buffers or something even more exotic. + + pvrusb2-main.c - This is the top level of the driver. Module level + and USB core entry points are here. This is our "main". + + pvrusb2-sysfs.[ch] - This is the high level interface which ties the + pvrusb2 driver into sysfs. Through this interface you can do + everything with the driver except actually stream data. + + pvrusb2-tuner.[ch] - This is glue logic that resides between this + driver and the tuner.ko I2C client driver (which is found + elsewhere in V4L). + + pvrusb2-util.h - This header defines some common macros used + throughout the driver. These macros are not really specific to + the driver, but they had to go somewhere. + + pvrusb2-v4l2.[ch] - This is the high level interface which ties the + pvrusb2 driver into video4linux. It is through here that V4L + applications can open and operate the driver in the usual V4L + ways. Note that **ALL** V4L functionality is published only + through here and nowhere else. + + pvrusb2-video-*.[ch] - This is glue logic that resides between this + driver and the saa711x.ko I2C client driver (which is found + elsewhere in V4L). Note that saa711x.ko used to be known as + saa7115.ko in ivtv. There are two versions of this; one is + selected depending on the particular saa711[5x].ko that is found. + + pvrusb2.h - This header contains compile time tunable parameters + (and at the moment the driver has very little that needs to be + tuned). + + + -Mike Isely + isely@pobox.com + diff --git a/Documentation/watchdog/pcwd-watchdog.txt b/Documentation/watchdog/pcwd-watchdog.txt index 12187a33e310..d9ee6336c1d4 100644 --- a/Documentation/watchdog/pcwd-watchdog.txt +++ b/Documentation/watchdog/pcwd-watchdog.txt @@ -22,78 +22,9 @@ to run the program with an "&" to run it in the background!) If you want to write a program to be compatible with the PC Watchdog - driver, simply do the following: - --- Snippet of code -- -/* - * Watchdog Driver Test Program - */ - -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <unistd.h> -#include <fcntl.h> -#include <sys/ioctl.h> -#include <linux/types.h> -#include <linux/watchdog.h> - -int fd; - -/* - * This function simply sends an IOCTL to the driver, which in turn ticks - * the PC Watchdog card to reset its internal timer so it doesn't trigger - * a computer reset. - */ -void keep_alive(void) -{ - int dummy; - - ioctl(fd, WDIOC_KEEPALIVE, &dummy); -} - -/* - * The main program. Run the program with "-d" to disable the card, - * or "-e" to enable the card. - */ -int main(int argc, char *argv[]) -{ - fd = open("/dev/watchdog", O_WRONLY); - - if (fd == -1) { - fprintf(stderr, "Watchdog device not enabled.\n"); - fflush(stderr); - exit(-1); - } - - if (argc > 1) { - if (!strncasecmp(argv[1], "-d", 2)) { - ioctl(fd, WDIOC_SETOPTIONS, WDIOS_DISABLECARD); - fprintf(stderr, "Watchdog card disabled.\n"); - fflush(stderr); - exit(0); - } else if (!strncasecmp(argv[1], "-e", 2)) { - ioctl(fd, WDIOC_SETOPTIONS, WDIOS_ENABLECARD); - fprintf(stderr, "Watchdog card enabled.\n"); - fflush(stderr); - exit(0); - } else { - fprintf(stderr, "-d to disable, -e to enable.\n"); - fprintf(stderr, "run by itself to tick the card.\n"); - fflush(stderr); - exit(0); - } - } else { - fprintf(stderr, "Watchdog Ticking Away!\n"); - fflush(stderr); - } - - while(1) { - keep_alive(); - sleep(1); - } -} --- End snippet -- + driver, simply use of modify the watchdog test program: + Documentation/watchdog/src/watchdog-test.c + Other IOCTL functions include: diff --git a/Documentation/watchdog/src/watchdog-simple.c b/Documentation/watchdog/src/watchdog-simple.c new file mode 100644 index 000000000000..85cf17c48669 --- /dev/null +++ b/Documentation/watchdog/src/watchdog-simple.c @@ -0,0 +1,15 @@ +#include <stdlib.h> +#include <fcntl.h> + +int main(int argc, const char *argv[]) { + int fd = open("/dev/watchdog", O_WRONLY); + if (fd == -1) { + perror("watchdog"); + exit(1); + } + while (1) { + write(fd, "\0", 1); + fsync(fd); + sleep(10); + } +} diff --git a/Documentation/watchdog/src/watchdog-test.c b/Documentation/watchdog/src/watchdog-test.c new file mode 100644 index 000000000000..65f6c19cb865 --- /dev/null +++ b/Documentation/watchdog/src/watchdog-test.c @@ -0,0 +1,68 @@ +/* + * Watchdog Driver Test Program + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> +#include <fcntl.h> +#include <sys/ioctl.h> +#include <linux/types.h> +#include <linux/watchdog.h> + +int fd; + +/* + * This function simply sends an IOCTL to the driver, which in turn ticks + * the PC Watchdog card to reset its internal timer so it doesn't trigger + * a computer reset. + */ +void keep_alive(void) +{ + int dummy; + + ioctl(fd, WDIOC_KEEPALIVE, &dummy); +} + +/* + * The main program. Run the program with "-d" to disable the card, + * or "-e" to enable the card. + */ +int main(int argc, char *argv[]) +{ + fd = open("/dev/watchdog", O_WRONLY); + + if (fd == -1) { + fprintf(stderr, "Watchdog device not enabled.\n"); + fflush(stderr); + exit(-1); + } + + if (argc > 1) { + if (!strncasecmp(argv[1], "-d", 2)) { + ioctl(fd, WDIOC_SETOPTIONS, WDIOS_DISABLECARD); + fprintf(stderr, "Watchdog card disabled.\n"); + fflush(stderr); + exit(0); + } else if (!strncasecmp(argv[1], "-e", 2)) { + ioctl(fd, WDIOC_SETOPTIONS, WDIOS_ENABLECARD); + fprintf(stderr, "Watchdog card enabled.\n"); + fflush(stderr); + exit(0); + } else { + fprintf(stderr, "-d to disable, -e to enable.\n"); + fprintf(stderr, "run by itself to tick the card.\n"); + fflush(stderr); + exit(0); + } + } else { + fprintf(stderr, "Watchdog Ticking Away!\n"); + fflush(stderr); + } + + while(1) { + keep_alive(); + sleep(1); + } +} diff --git a/Documentation/watchdog/watchdog-api.txt b/Documentation/watchdog/watchdog-api.txt index 21ed51173662..958ff3d48be3 100644 --- a/Documentation/watchdog/watchdog-api.txt +++ b/Documentation/watchdog/watchdog-api.txt @@ -34,22 +34,7 @@ activates as soon as /dev/watchdog is opened and will reboot unless the watchdog is pinged within a certain time, this time is called the timeout or margin. The simplest way to ping the watchdog is to write some data to the device. So a very simple watchdog daemon would look -like this: - -#include <stdlib.h> -#include <fcntl.h> - -int main(int argc, const char *argv[]) { - int fd=open("/dev/watchdog",O_WRONLY); - if (fd==-1) { - perror("watchdog"); - exit(1); - } - while(1) { - write(fd, "\0", 1); - sleep(10); - } -} +like this source file: see Documentation/watchdog/src/watchdog-simple.c A more advanced driver could for example check that a HTTP server is still responding before doing the write call to ping the watchdog. @@ -110,7 +95,40 @@ current timeout using the GETTIMEOUT ioctl. ioctl(fd, WDIOC_GETTIMEOUT, &timeout); printf("The timeout was is %d seconds\n", timeout); -Envinronmental monitoring: +Pretimeouts: + +Some watchdog timers can be set to have a trigger go off before the +actual time they will reset the system. This can be done with an NMI, +interrupt, or other mechanism. This allows Linux to record useful +information (like panic information and kernel coredumps) before it +resets. + + pretimeout = 10; + ioctl(fd, WDIOC_SETPRETIMEOUT, &pretimeout); + +Note that the pretimeout is the number of seconds before the time +when the timeout will go off. It is not the number of seconds until +the pretimeout. So, for instance, if you set the timeout to 60 seconds +and the pretimeout to 10 seconds, the pretimout will go of in 50 +seconds. Setting a pretimeout to zero disables it. + +There is also a get function for getting the pretimeout: + + ioctl(fd, WDIOC_GETPRETIMEOUT, &timeout); + printf("The pretimeout was is %d seconds\n", timeout); + +Not all watchdog drivers will support a pretimeout. + +Get the number of seconds before reboot: + +Some watchdog drivers have the ability to report the remaining time +before the system will reboot. The WDIOC_GETTIMELEFT is the ioctl +that returns the number of seconds before reboot. + + ioctl(fd, WDIOC_GETTIMELEFT, &timeleft); + printf("The timeout was is %d seconds\n", timeleft); + +Environmental monitoring: All watchdog drivers are required return more information about the system, some do temperature, fan and power level monitoring, some can tell you @@ -169,6 +187,10 @@ The watchdog saw a keepalive ping since it was last queried. WDIOF_SETTIMEOUT Can set/get the timeout +The watchdog can do pretimeouts. + + WDIOF_PRETIMEOUT Pretimeout (in seconds), get/set + For those drivers that return any bits set in the option field, the GETSTATUS and GETBOOTSTATUS ioctls can be used to ask for the current diff --git a/Documentation/watchdog/watchdog.txt b/Documentation/watchdog/watchdog.txt index dffda29c8799..4b1ff69cc19a 100644 --- a/Documentation/watchdog/watchdog.txt +++ b/Documentation/watchdog/watchdog.txt @@ -65,28 +65,7 @@ The external event interfaces on the WDT boards are not currently supported. Minor numbers are however allocated for it. -Example Watchdog Driver ------------------------ - -#include <stdio.h> -#include <unistd.h> -#include <fcntl.h> - -int main(int argc, const char *argv[]) -{ - int fd=open("/dev/watchdog",O_WRONLY); - if(fd==-1) - { - perror("watchdog"); - exit(1); - } - while(1) - { - write(fd,"\0",1); - fsync(fd); - sleep(10); - } -} +Example Watchdog Driver: see Documentation/watchdog/src/watchdog-simple.c Contact Information |