Add a generic associative array implementation that can be used as the
container for keyrings, thereby massively increasing the capacity available
whilst also speeding up searching in keyrings that contain a lot of keys.
This may also be useful in FS-Cache for tracking cookies.
Documentation is added into Documentation/associative_array.txt
Some of the properties of the implementation are:
(1) Objects are opaque pointers. The implementation does not care where they
point (if anywhere) or what they point to (if anything).
[!] NOTE: Pointers to objects _must_ be zero in the two least significant
bits.
(2) Objects do not need to contain linkage blocks for use by the array. This
permits an object to be located in multiple arrays simultaneously.
Rather, the array is made up of metadata blocks that point to objects.
(3) Objects are labelled as being one of two types (the type is a bool value).
This information is stored in the array, but has no consequence to the
array itself or its algorithms.
(4) Objects require index keys to locate them within the array.
(5) Index keys must be unique. Inserting an object with the same key as one
already in the array will replace the old object.
(6) Index keys can be of any length and can be of different lengths.
(7) Index keys should encode the length early on, before any variation due to
length is seen.
(8) Index keys can include a hash to scatter objects throughout the array.
(9) The array can iterated over. The objects will not necessarily come out in
key order.
(10) The array can be iterated whilst it is being modified, provided the RCU
readlock is being held by the iterator. Note, however, under these
circumstances, some objects may be seen more than once. If this is a
problem, the iterator should lock against modification. Objects will not
be missed, however, unless deleted.
(11) Objects in the array can be looked up by means of their index key.
(12) Objects can be looked up whilst the array is being modified, provided the
RCU readlock is being held by the thread doing the look up.
The implementation uses a tree of 16-pointer nodes internally that are indexed
on each level by nibbles from the index key. To improve memory efficiency,
shortcuts can be emplaced to skip over what would otherwise be a series of
single-occupancy nodes. Further, nodes pack leaf object pointers into spare
space in the node rather than making an extra branch until as such time an
object needs to be added to a full node.
Signed-off-by: David Howells <dhowells@redhat.com>
Define a __key_get() wrapper to use rather than atomic_inc() on the key usage
count as this makes it easier to hook in refcount error debugging.
Signed-off-by: David Howells <dhowells@redhat.com>
Search functions pass around a bunch of arguments, each of which gets copied
with each call. Introduce a search context structure to hold these.
Whilst we're at it, create a search flag that indicates whether the search
should be directly to the description or whether it should iterate through all
keys looking for a non-description match.
This will be useful when keyrings use a generic data struct with generic
routines to manage their content as the search terms can just be passed
through to the iterator callback function.
Also, for future use, the data to be supplied to the match function is
separated from the description pointer in the search context. This makes it
clear which is being supplied.
Signed-off-by: David Howells <dhowells@redhat.com>
Consolidate the concept of an 'index key' for accessing keys. The index key
is the search term needed to find a key directly - basically the key type and
the key description. We can add to that the description length.
This will be useful when turning a keyring into an associative array rather
than just a pointer block.
Signed-off-by: David Howells <dhowells@redhat.com>
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.14 (GNU/Linux)
iQEcBAABAgAGBQJSQMORAAoJEHm+PkMAQRiGj14H/1bjhtfNjPdX7MVQAzA+WpwX
s7h1IQu2Si9S5S1lBiM2sBTOssVcmfheO9x4yqm7JNOD1RnssWKOM3q+zVOLstwd
GD3gluJPeraD5EyYSqEJ9ILPQ3gbxb4wOlT0Z291TW6E8XhLRr0RTOJPksRsgvLH
Ckm9uJh6ArS6ZXfXiaDQfd+xHAQJkUfW6nMSA0g9ZO9C6KIDRvcbUmrY3m4HhfIk
mK0TXCBs+AXGDIjTEB8JgIQL/5y1Qn0c4R+2uTU/4YWwyLvJTV1e44kGoleukMMT
6Pw/TNlUEN161dbSaqCyF3sfXHDYQ5valycI2PDgitMtPSxbzsU1VDizS8+daRg=
=lEmF
-----END PGP SIGNATURE-----
Merge tag 'v3.12-rc2' into drm-intel-next
Backmerge Linux 3.12-rc2 to prep for a bunch of -next patches:
- Header cleanup in intel_drv.h, both changed in -fixes and my current
-next pile.
- Cursor handling cleanup for -next which depends upon the cursor
handling fix merged into -rc2.
All just trivial conflicts of the "changed adjacent lines" type:
drivers/gpu/drm/i915/i915_gem.c
drivers/gpu/drm/i915/intel_display.c
drivers/gpu/drm/i915/intel_drv.h
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Modify DaVinci GPIO driver to become a platform device
driver.
The driver does not have platform driver structure or
a probe. Instead, it has pure_initcall function for
initialization. The platform specific informaiton is
obtained using the DaVinci specific davinci_soc_info
structure. This is a problem for Device Tree (DT)
implementation.
As a first stage of DT conversion, we implement a probe.
Additional notes:
- The driver registration happens as postcore_initcall.
This is required since machine init functions like
da850_lcd_hw_init() make use of GPIO.
- Start using devres APIs for simpler error handling.
Signed-off-by: KV Sujith <sujithkv@ti.com>
[avinashphilip@ti.com: Move global definition of
"davinci_gpio_controller" to local]
Signed-off-by: Philip Avinash <avinashphilip@ti.com>
Acked-by: Linus Walleij <linus.walleij@linaro.org>
[nsekhar@ti.com: drop unused structure member, rebase to new
clean-up patch and fix error messages]
Signed-off-by: Sekhar Nori <nsekhar@ti.com>
Signed-off-by: Lad, Prabhakar <prabhakar.csengg@gmail.com>
The only user of css_id was memcg, and it has been convered to use
cgroup->id, so kill css_id.
Signed-off-by: Li Zefan <lizefan@huwei.com>
Reviewed-by: Michal Hocko <mhocko@suse.cz>
Acked-by: Tejun Heo <tj@kernel.org>
Signed-off-by: Tejun Heo <tj@kernel.org>
* pci/yijing-pci_is_pcie-v2:
powerpc/pci: Use pci_is_pcie() to simplify code
[SCSI] qla2xxx: Use pcie_is_pcie() to simplify code
[SCSI] csiostor: Use pcie_capability_clear_and_set_word() to simplify code
[SCSI] bfa: Use pcie_set()/get_readrq() to simplify code
x86/pci: Use cached pci_dev->pcie_cap to simplify code
PCI: Use pci_is_pcie() to simplify code
Version 20130823.
Signed-off-by: Bob Moore <robert.moore@intel.com>
Signed-off-by: Lv Zheng <lv.zheng@intel.com>
Reviewed-by: Len Brown <len.brown@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
The SCI interrupt number is not needed for the SCI handlers, and was
just unnecessary overhead.
Signed-off-by: Bob Moore <robert.moore@intel.com>
Signed-off-by: Lv Zheng <lv.zheng@intel.com>
Reviewed-by: Len Brown <len.brown@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
This patch adds AE_ACCESS for EACCES or EPERM. Some error prompts are
also cleaned up in this patch. Lv Zheng.
Signed-off-by: Lv Zheng <lv.zheng@intel.com>
Signed-off-by: Bob Moore <robert.moore@intel.com>
Reviewed-by: Len Brown <len.brown@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
This patch introduces new macors to handle RSDP signature and cleans up the
affected codes. Lv Zheng.
Some updates are only used for ACPICA utilities which are not shipped in
the kernel yet.
Signed-off-by: Lv Zheng <lv.zheng@intel.com>
Signed-off-by: Bob Moore <robert.moore@intel.com>
Reviewed-by: Len Brown <len.brown@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
This change adds support to allow hosts to install System Control
Interrupt handlers. Certain ACPI functionality requires the host
to handle raw SCIs. For example, the "SCI Doorbell" that is defined
for memory power state support requires the host device driver to
handle SCIs to examine if the doorbell has been activated. Multiple
SCI handlers can be installed to allow for future expansion.
Debugger support is included.
Lv Zheng, Bob Moore. ACPICA BZ 1032.
Bug summary:
It is reported when the PCC (Platform Communication Channel, via
MPST table, defined in ACPI specification 5.0) subchannel responds
to the host, it issues an SCI and the host must probe the subchannel
for channel status.
Buglink: http://bugs.acpica.org/show_bug.cgi?id=1032
Signed-off-by: Lv Zheng <lv.zheng@intel.com>
Signed-off-by: Bob Moore <robert.moore@intel.com>
Reviewed-by: Len Brown <len.brown@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Add support for the __aarch64__ define for 64-bit builds.
Signed-off-by: Naresh Bhat <naresh.bhat@linaro.org>
Signed-off-by: Bob Moore <robert.moore@intel.com>
Signed-off-by: Lv Zheng <lv.zheng@intel.com>
Reviewed-by: Len Brown <len.brown@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Make PCI Host Bridge _OSC #defines more consistent. No functional change.
Signed-off-by: Bjorn Helgaas <bhelgaas@google.com>
Acked-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
We write OSC_PCI_SUPPORT_MASKS as a simple 0x1f, so do the same
for OSC_PCI_CONTROL_MASKS. No functional change.
Signed-off-by: Bjorn Helgaas <bhelgaas@google.com>
Acked-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
OSC_PCI_NATIVE_HOTPLUG is completely unused, so remove it. No functional
change.
Signed-off-by: Bjorn Helgaas <bhelgaas@google.com>
Acked-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Move the acpi_run_osc() prototype next to the related structure and
update comments. No functional change.
Signed-off-by: Bjorn Helgaas <bhelgaas@google.com>
Acked-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
OSC_QUERY_TYPE isn't a "type"; it's an index into the _OSC Capabilities
Buffer of DWORDs. Rename OSC_QUERY_TYPE, OSC_SUPPORT_TYPE, and
OSC_CONTROL_TYPE to OSC_QUERY_DWORD, etc., to make this clear.
No functional change.
Signed-off-by: Bjorn Helgaas <bhelgaas@google.com>
Acked-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Update _OSC definition comments to correspond to the 1-based spec wording
(DWORD 1, etc.) Write _OSC field #defines as hex to make clear that they
are bits in a 32-bit DWORD, not arbitrary values. No functional change.
Signed-off-by: Bjorn Helgaas <bhelgaas@google.com>
Acked-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Since APIC id is saved in processor struct, just use it and
remove the duplicated _MAT evaluation.
Signed-off-by: Jiang Liu <jiang.liu@huawei.com>
Signed-off-by: Hanjun Guo <hanjun.guo@linaro.org>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
For cpu hot add, we evaluate _MAT or parse MADT twice to get APIC id,
here is the code logic:
acpi_processor_add()
acpi_processor_get_info()
acpi_get_cpuid() will evaluate _MAT or parse MADT;
acpi_processor_hotadd_init()
acpi_map_lsapic() will evaluate _MAT again;
This can be done more effectively, this patch introduces apic_id in struct
processor to save parsed APIC id, and then we can use it and remove the
duplicated _MAT evaluation.
Signed-off-by: Jiang Liu <jiang.liu@huawei.com>
Signed-off-by: Hanjun Guo <hanjun.guo@linaro.org>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
pci_is_pcie() and pcie_capability_clear_and_set_word() make it trivial
to set the PCIe Completion Timeout, so just fold the
csio_set_pcie_completion_timeout() function into its caller.
[bhelgaas: changelog, fold csio_set_pcie_completion_timeout() into caller]
Signed-off-by: Yijing Wang <wangyijing@huawei.com>
Signed-off-by: Bjorn Helgaas <bhelgaas@google.com>
Cc: Jiang Liu <jiang.liu@huawei.com>
Cc: "James E.J. Bottomley" <JBottomley@parallels.com>
Cc: Naresh Kumar Inna <naresh@chelsio.com>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Jesper Juhl <jj@chaosbits.net>
When tracing switching, an external tracer needs a way to bootstrap
its knowledge of the logical<->physical CPU mapping.
This patch adds a sysfs attribute trace_trigger. A write to this
attribute will generate a power:cpu_migrate_current event for each
online CPU, indicating the current physical CPU for each logical
CPU.
Activating or deactivating the switcher also generates these
events, so that the tracer knows about the resulting remapping of
affected CPUs.
Signed-off-by: Dave Martin <dave.martin@linaro.org>
This patch adds simple trace events to the b.L switcher code
to allow tracing of CPU migration events.
To make use of the trace events, you will need:
CONFIG_FTRACE=y
CONFIG_ENABLE_DEFAULT_TRACERS=y
The following events are added:
* power:cpu_migrate_begin
* power:cpu_migrate_finish
each with the following data:
u64 timestamp;
u32 cpu_hwid;
power:cpu_migrate_begin occurs immediately before the
switcher-specific migration operations start.
power:cpu_migrate_finish occurs immediately when migration is
completed.
The cpu_hwid field contains the ID fields of the MPIDR.
* For power:cpu_migrate_begin, cpu_hwid is the ID of the outbound
physical CPU (equivalent to (from_phys_cpu,from_phys_cluster)).
* For power:cpu_migrate_finish, cpu_hwid is the ID of the inbound
physical CPU (equivalent to (to_phys_cpu,to_phys_cluster)).
By design, the cpu_hwid field is masked in the same way as the
device tree cpu node reg property, allowing direct correlation to
the DT description of the hardware.
The timestamp is added in order to minimise timing noise. An
accurate system-wide clock should be used for generating this
(hopefully getnstimeofday is appropriate, but it could be changed).
It could be any monotonic shared clock, since the aim is to allow
accurate deltas to be computed. We don't necessarily care about
accurate synchronisation with wall clock time.
In practice, each switch takes place on a single logical CPU,
and the trace infrastructure should guarantee that events are
well-ordered with respect to a single logical CPU.
Signed-off-by: Dave Martin <dave.martin@linaro.org>
Signed-off-by: Nicolas Pitre <nico@linaro.org>
The regular gic_raise_softirq() takes as input a CPU mask which is not
adequate when we need to send an IPI to a CPU which is not represented
in the kernel to GIC mapping. That is the case with the b.L switcher
when GIC migration to the inbound CPU has not yet occurred.
Signed-off-by: Nicolas Pitre <nico@linaro.org>
In order to have early assembly code signal other CPUs in the system,
we need to get the physical address for the SGIR register used to
send IPIs. Because the register will be used with a precomputed CPU
interface ID number, there is no need for any locking in the assembly
code where this register is written to.
Signed-off-by: Nicolas Pitre <nico@linaro.org>
MRP doesn't implement the periodictimer in 802.1Q, so it never retries
if packets get lost. I ran into this problem when MRP sent a MVRP
JoinIn before the interface was fully up. The JoinIn was lost, MRP
didn't retry, and MVRP registration failed.
Tested against Juniper QFabric switches
Signed-off-by: Noel Burton-Krahn <noel@burton-krahn.com>
Acked-by: David Ward <david.ward@ll.mit.edu>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Acked-by: Vlad Yasevich <vyasevich@gmail.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
There are a mix of function prototypes with and without extern
in the kernel sources. Standardize on not using extern for
function prototypes.
Function prototypes don't need to be written with extern.
extern is assumed by the compiler. Its use is as unnecessary as
using auto to declare automatic/local variables in a block.
Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
We have USB fixes now in Linus's tree that we need to properly sort out
with reverts and the like in the usb-next branch, so merge them together
and do it by hand.
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Create a generic version of ablk_helper so it can be reused
by other architectures.
Acked-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
Signed-off-by: Ard Biesheuvel <ard.biesheuvel@linaro.org>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
The power to some of the sensors are controlled by regulators. In most
cases these are 'always on', but if not they will fail to work until
the regulator is enabled using the relevant APIs. This patch allows for
the Vdd_IO power supply to be specified by either platform data or
Device Tree.
Signed-off-by: Lee Jones <lee.jones@linaro.org>
Signed-off-by: Jonathan Cameron <jic23@kernel.org>
The power to some of the sensors are controlled by regulators. In most
cases these are 'always on', but if not they will fail to work until
the regulator is enabled using the relevant APIs. This patch allows for
the Vdd power supply to be specified by either platform data or Device
Tree.
Signed-off-by: Lee Jones <lee.jones@linaro.org>
Signed-off-by: Jonathan Cameron <jic23@kernel.org>
The event-tracing macros do not like bool tracing arguments, so this
commit makes them be of type char. This change has the knock-on effect
of making it illegal to pass a pointer into one of these arguments, so
also change rcutiny's first call to trace_rcu_batch_end() to convert
from pointer to boolean, prefixing with "!!".
Reported-by: kbuild test robot <fengguang.wu@intel.com>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
This commit adds event traces to track all of rcu_nocb_kthread()'s
blocking and awakening.
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Lost wakeups from call_rcu() to the rcuo kthreads can result in hangs
that are difficult to diagnose. This commit therefore adds tracing to
help pin down the cause of these hangs.
Reported-by: Clark Williams <williams@redhat.com>
Reported-by: Carsten Emde <C.Emde@osadl.org>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
[ paulmck: Add const per kbuild test robot's advice. ]
This commit adds tracing to the normal grace-period request points.
These are rcu_gp_cleanup(), which checks for the need for another
grace period at the end of the previous grace period, and
rcu_start_gp_advanced(), which restarts RCU's state machine after
an idle period. These trace events are intended to help track down
bugs where RCU remains idle despite there being work for it to do.
Reported-by: Clark Williams <williams@redhat.com>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
This commit adds tracing to the rcu_gp_kthread() function in order to
help trace down hangs potentially involving this kthread.
Reported-by: Clark Williams <williams@redhat.com>
Reported-by: Carsten Emde <C.Emde@osadl.org>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
