block: prepare I/O context code for BFQ-v4 for 2.6.38

BFQ uses struct cfq_io_context to store its per-process per-device data,
reusing the same code for cic handling of CFQ.  The code is not shared
ATM to minimize the impact of these patches.

This patch introduces a new hlist to each io_context to store all the
cic's allocated by BFQ to allow calling the right destructor on module
unload; the radix tree used for cic lookup needs to be duplicated
because it can contain dead keys inserted by a scheduler and later
retrieved by the other one.

Update the io_context exit and free paths to take care also of
the BFQ cic's.

Change the type of cfqq inside struct cfq_io_context to void *
to use it also for BFQ per-queue data.

A new bfq-specific ioprio_changed field is necessary, too, to avoid
clobbering cfq's one, so switch ioprio_changed to a bitmap, with one
element per scheduler.

Signed-off-by: Fabio Checconi <fabio@gandalf.sssup.it>
Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
block: cgroups, kconfig, build bits for BFQ-v4-2.6.38

Add a Kconfig option and do the related Makefile changes to compile
the BFQ I/O scheduler.  Also let the cgroups subsystem know about the
BFQ I/O controller.

Signed-off-by: Fabio Checconi <fabio@gandalf.sssup.it>
Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
block: introduce the BFQ-v4 I/O sched for 2.6.38

Add the BFQ-v4 I/O scheduler to 2.6.38.
The general structure is borrowed from CFQ, as much code. A (bfq_)queue is
associated to each task doing I/O on a device, and each time a scheduling
decision has to be taken a queue is selected and it is served until it expires.

    - Slices are given in the service domain: tasks are assigned budgets,
      measured in number of sectors. Once got the disk, a task must
      however consume its assigned budget within a configurable maximum time
      (by default, the maximum possible value of the budgets is automatically
      computed to comply with this timeout). This allows the desired latency
      vs "throughput boosting" tradeoff to be set.

    - Budgets are scheduled according to a variant of WF2Q+, implemented
      using an augmented rb-tree to take eligibility into account while
      preserving an O(log N) overall complexity.

    - A low-latency tunable is provided; if enabled, both interactive and soft
      real-time applications are guaranteed very low latency.

    - Latency guarantees are preserved also in presence of NCQ.

    - High throughput with flash-based devices, while still preserving
      latency guarantees.

    - Useful features borrowed from CFQ: cooperating-queues merging (with
      some additional optimizations with respect to the original CFQ version),
      static fallback queue for OOM.

    - BFQ supports full hierarchical scheduling, exporting a cgroups
      interface.  Each node has a full scheduler, so each group can
      be assigned its own ioprio and an ioprio_class.

    - If the cgroups interface is used, weights can be explictly assigned,
      otherwise ioprio values are mapped to weights using the relation
      weight = IOPRIO_BE_NR - ioprio.

    - ioprio classes are served in strict priority order, i.e., lower
      priority queues are not served as long as there are higher priority
      queues.  Among queues in the same class the bandwidth is distributed
      in proportion to the weights of each queue. A very thin extra bandwidth
      is however guaranteed to the Idle class, to prevent it from starving.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
rtlwifi: Eliminate udelay calls with too large values

On ARM, compilation of rtlwifi/efuse.c fails with the message:
ERROR: "__bad_udelay" [drivers/net/wireless/rtlwifi/rtlwifi.ko] undefined!
On inspection, the faulty calls are in routine efuse_reset_loader(), a
routine that is never used, and the faulty routine is deleted.

Signed-off-by: Willy Tarreau <w@...>
Signed-off-by: Larry Finger <Larry.Finger@...>
Signed-off-by: John W. Linville <linville@...>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
tcp: Increase the initial congestion window to 10.

Signed-off-by: David S. Miller <davem@davemloft.net>
Acked-by: Nandita Dukkipati <nanditad@google.com>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
staging: zcache: in-kernel tmem code

[PATCH V2 1/3] drivers/staging: zcache: in-kernel tmem code

Transcendent memory ("tmem") is a clean API/ABI that provides
for an efficient address translation and a set of highly
concurrent access methods to copy data between a page-oriented
data source (e.g. cleancache or frontswap) and a page-addressable
memory ("PAM") data store.  Of critical importance, the PAM data
store is of unknown (and possibly varying) size so any individual
access may succeed or fail as defined by the API/ABI.

Tmem exports a basic set of access methods (e.g. put, get,
flush, flush object, new pool, and destroy pool) which are
normally called from a "host" (e.g. zcache).

To be functional, two sets of "ops" must be registered by the
host, one to provide "host services" (memory allocation) and
one to provide page-addressable memory ("PAM") hooks.

Tmem supports one or more "clients", each which can provide
a set of "pools" to partition pages.  Each pool contains
a set of "objects"; each object holds pointers to some number
of PAM page descriptors ("pampd"), indexed by an "index" number.
This triple <pool id, object id, index> is sometimes referred
to as a "handle".  Tmem's primary function is to essentially
provide address translation of handles into pampds and move
data appropriately.

As an example, for cleancache, a pool maps to a filesystem,
an object maps to a file, and the index is the page offset
into the file.  And in this patch, zcache is the host and
each PAM descriptor points to a compressed page of data.

Tmem supports two kinds of pages: "ephemeral" and "persistent".
Ephemeral pages may be asynchronously reclaimed "bottoms up"
so the data structures and concurrency model must allow for
this.  For example, each pampd must retain sufficient information
to invalidate tmem's handle-to-pampd translation.
its containing object so that, on reclaim, all tmem data
structures can be made consistent.

Signed-off-by: Dan Magenheimer <dan.magenheimer@oracle.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
staging: zcache: misc build/config

[PATCH V2 3/3] drivers/staging: zcache: misc build/config

Makefiles and Kconfigs to build zcache in drivers/staging

There is a dependency on xvmalloc.* which in 2.6.37 resides
in drivers/staging/zram.  Should this move or disappear,
some Makefile/Kconfig changes will be required.

Signed-off-by: Dan Magenheimer <dan.magenheimer@oracle.com>
Signed-off-by: Nitin Gupta <ngupta@vflare.org>
Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
staging: zcache: host services and PAM services

[PATCH V2 2/3] drivers/staging: zcache: host services and PAM services

Zcache provides host services (memory allocation) for tmem,
a "shim" to interface cleancache and frontswap to tmem, and
two different page-addressable memory implemenations using
lzo1x compression.  The first, "compression buddies" ("zbud")
compresses pairs of pages and supplies a shrinker interface
that allows entire pages to be reclaimed.  The second is
a shim to xvMalloc which is more space-efficient but
less receptive to page reclamation.  The first is used
for ephemeral pools and the second for persistent pools.
All ephemeral pools share the same memory, that is, even
pages from different pools can share the same page.

Signed-off-by: Dan Magenheimer <dan.magenheimer@oracle.com>
Signed-off-by: Nitin Gupta <ngupta@vflare.org>
Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
add .gitignore
Makefile: use toolchain
crypto: authencesn - Add algorithm to handle IPsec extended sequence numbers

ESP with separate encryption/authentication algorithms needs a special
treatment for the associated data. This patch add a new algorithm that
handles esp with extended sequence numbers.

Signed-off-by: Steffen Klassert <steffen.klassert@secunet.com>
Acked-by: Herbert Xu <herbert@gondor.apana.org.au>
Signed-off-by: David S. Miller <davem@davemloft.net>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
Subject: [PATCH] Smack: mmap controls for library containment

  In the embedded world there are often situations
  where libraries are updated from a variety of sources,
  for a variety of reasons, and with any number of
  security characteristics. These differences
  might include privilege required for a given library
  provided interface to function properly, as occurs
  from time to time in graphics libraries. There are
  also cases where it is important to limit use of
  libraries based on the provider of the library and
  the security aware application may make choices
  based on that criteria.

  These issues are addressed by providing an additional
  Smack label that may optionally be assigned to an object,
  the SMACK64MMAP attribute. An mmap operation is allowed
  if there is no such attribute.

  If there is a SMACK64MMAP attribute the mmap is permitted
  only if a subject with that label has all of the access
  permitted a subject with the current task label.

  Security aware applications may from time to time
  wish to reduce their "privilege" to avoid accidental use
  of privilege. One case where this arises is the
  environment in which multiple sources provide libraries
  to perform the same functions. An application may know
  that it should eschew services made available from a
  particular vendor, or of a particular version.

  In support of this a secondary list of Smack rules has
  been added that is local to the task. This list is
  consulted only in the case where the global list has
  approved access. It can only further restrict access.
  Unlike the global last, if no entry is found on the
  local list access is granted. An application can add
  entries to its own list by writing to /smack/load-self.

  The changes appear large as they involve refactoring
  the list handling to accomodate there being more
  than one rule list.

Signed-off-by: Casey Schaufler <casey@schaufler-ca.com>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
SELinux: Use dentry name in new object labeling

Currently SELinux has rules which label new objects according to 3 criteria.
The label of the process creating the object, the label of the parent
directory, and the type of object (reg, dir, char, block, etc.)  This patch
adds a 4th criteria, the dentry name, thus we can distinguish between
creating a file in an etc_t directory called shadow and one called motd.

There is no file globbing, regex parsing, or anything mystical.  Either the
policy exactly (strcmp) matches the dentry name of the object or it doesn't.
This patch has no changes from today if policy does not implement the new
rules.

Signed-off-by: Eric Paris <eparis@redhat.com>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
Allow user names longer than 32 bytes

We artificially limited the user name to 32 bytes, but modern servers handle
larger.  Set the maximum length to a reasonable 256, and make the user name
string dynamically allocated rather than a fixed size in session structure.
Also clean up old checkpatch warning.

Signed-off-by: Steve French <sfrench@us.ibm.com>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
dm stripe: implement merge method

Implement a merge function in the striped target.

When the striped target's underlying devices provide a merge_bvec_fn
(like all DM devices do via dm_merge_bvec) it is important to call down
to them when building a biovec that doesn't span a stripe boundary.

Without the merge method, a striped DM device stacked on DM devices
causes bios with a single page to be submitted which results
in unnecessary overhead that hurts performance.

This change really helps filesystems (e.g. XFS and now ext4) which take
care to assemble larger bios.  By implementing stripe_merge(), DM and the
stripe target no longer undermine the filesystem's work by only allowing
a single page per bio.  Buffered IO sees the biggest improvement
(particularly uncached reads, buffered writes to a lesser degree).  This
is especially so for more capable "enterprise" storage LUNs.

The performance improvement has been measured to be ~12-35% -- when a
reasonable chunk_size is used (e.g. 64K) in conjunction with a stripe
count that is a power of 2.

In contrast, the performance penalty is ~5-7% for the pathological worst
case stripe configuration (small chunk_size with a stripe count that is
not a power of 2).  The reason for this is that stripe_map_sector() is
now called once for every call to dm_merge_bvec().  stripe_map_sector()
will use slower division if stripe count isn't a power of 2.

Signed-off-by: Mustafa Mesanovic <mume@linux.vnet.ibm.com>
Signed-off-by: Mike Snitzer <snitzer@redhat.com>
Signed-off-by: Alasdair G Kergon <agk@redhat.com>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
dm: add flakey target

This target is the same as the linear target except that it returns I/O
errors periodically.  It's been found useful in simulating failing
devices for testing purposes.

I needed a dm target to do some failure testing on btrfs's raid code, and
Mike pointed me at this.

Signed-off-by: Josef Bacik <josef@redhat.com>
Signed-off-by: Alasdair G Kergon <agk@redhat.com>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
mm: vmap area cache

Provide a free area cache for the vmalloc virtual address allocator, based
on the algorithm used by the user virtual memory allocator.

This reduces the number of rbtree operations and linear traversals over
the vmap extents in order to find a free area, by starting off at the last
point that a free area was found.

The free area cache is reset if areas are freed behind it, or if we are
searching for a smaller area or alignment than last time.  So allocation
patterns are not changed (verified by corner-case and random test cases in
userspace testing).

This solves a regression caused by lazy vunmap TLB purging introduced in
db64fe02 (mm: rewrite vmap layer).  That patch will leave extents in the
vmap allocator after they are vunmapped, and until a significant number
accumulate that can be flushed in a single batch.  So in a workload that
vmalloc/vfree frequently, a chain of extents will build up from
VMALLOC_START address, which have to be iterated over each time (giving an
O(n) type of behaviour).

After this patch, the search will start from where it left off, giving
closer to an amortized O(1).

This is verified to solve regressions reported Steven in GFS2, and Avi in
KVM.

Hugh's update:

: I tried out the recent mmotm, and on one machine was fortunate to hit
: the BUG_ON(first->va_start < addr) which seems to have been stalling
: your vmap area cache patch ever since May.

: I can get you addresses etc, I did dump a few out; but once I stared
: at them, it was easier just to look at the code: and I cannot see how
: you would be so sure that first->va_start < addr, once you've done
: that addr = ALIGN(max(...), align) above, if align is over 0x1000
: (align was 0x8000 or 0x4000 in the cases I hit: ioremaps like Steve).

: I originally got around it by just changing the
: 		if (first->va_start < addr) {
: to
: 		while (first->va_start < addr) {
: without thinking about it any further; but that seemed unsatisfactory,
: why would we want to loop here when we've got another very similar
: loop just below it?

: I am never going to admit how long I've spent trying to grasp your
: "while (n)" rbtree loop just above this, the one with the peculiar
: 		if (!first && tmp->va_start < addr + size)
: in.  That's unfamiliar to me, I'm guessing it's designed to save a
: subsequent rb_next() in a few circumstances (at risk of then setting
: a wrong cached_hole_size?); but they did appear few to me, and I didn't
: feel I could sign off something with that in when I don't grasp it,
: and it seems responsible for extra code and mistaken BUG_ON below it.

: I've reverted to the familiar rbtree loop that find_vma() does (but
: with va_end >= addr as you had, to respect the additional guard page):
: and then (given that cached_hole_size starts out 0) I don't see the
: need for any complications below it.  If you do want to keep that loop
: as you had it, please add a comment to explain what it's trying to do,
: and where addr is relative to first when you emerge from it.

: Aren't your tests "size <= cached_hole_size" and
: "addr + size > first->va_start" forgetting the guard page we want
: before the next area?  I've changed those.

: I have not changed your many "addr + size - 1 < addr" overflow tests,
: but have since come to wonder, shouldn't they be "addr + size < addr"
: tests - won't the vend checks go wrong if addr + size is 0?

: I have added a few comments - Wolfgang Wander's 2.6.13 description of
: 1363c3cd8603a913a27e2995dccbd70d5312d8e6 Avoiding mmap fragmentation
: helped me a lot, perhaps a pointer to that would be good too.  And I found
: it easier to understand when I renamed cached_start slightly and moved the
: overflow label down.

: This patch would go after your mm-vmap-area-cache.patch in mmotm.
: Trivially, nobody is going to get that BUG_ON with this patch, and it
: appears to work fine on my machines; but I have not given it anything like
: the testing you did on your original, and may have broken all the
: performance you were aiming for.  Please take a look and test it out
: integrate with yours if you're satisfied - thanks.

[akpm@linux-foundation.org: add locking comment]
Signed-off-by: Nick Piggin <npiggin@suse.de>
Signed-off-by: Hugh Dickins <hughd@google.com>
Reviewed-by: Minchan Kim <minchan.kim@gmail.com>
Reported-and-tested-by: Steven Whitehouse <swhiteho@redhat.com>
Reported-and-tested-by: Avi Kivity <avi@redhat.com>
Tested-by: "Barry J. Marson" <bmarson@redhat.com>
Cc: Prarit Bhargava <prarit@redhat.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
sched: Allow users with sufficient RLIMIT_NICE to change from SCHED_IDLE policy

The current scheduler implementation returns -EPERM when trying to
change from SCHED_IDLE to SCHED_OTHER or SCHED_BATCH. Since SCHED_IDLE
is considered to be a nice 20 on steroids, changing to another policy
should be allowed provided the RLIMIT_NICE is accounted for.

This patch allows the following test-case to pass with RLIMIT_NICE=40,
but still fail with RLIMIT_NICE=10 when the calling process is run
from a typical shell (nice 0, or 20 in rlimit terms).

int main()
{
	int ret;
	struct sched_param sp;
	sp.sched_priority = 0;

	/* switch to SCHED_IDLE */
	ret = sched_setscheduler(0, SCHED_IDLE, &sp);
	printf("setscheduler IDLE: %d\n", ret);
	if (ret) return ret;

	/* switch back to SCHED_OTHER */
	ret = sched_setscheduler(0, SCHED_OTHER, &sp);
	printf("setscheduler OTHER: %d\n", ret);

	return ret;
}

 $ ulimit -e
 40
 $ ./test
 setscheduler IDLE: 0
 setscheduler OTHER: 0

 $ ulimit -e 10
 $ ulimit -e
 10
 $ ./test
 setscheduler IDLE: 0
 setscheduler OTHER: -1

Signed-off-by: Darren Hart <dvhart@linux.intel.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Richard Purdie <richard.purdie@linuxfoundation.org>
LKML-Reference: <4D657BEE.4040608@linux.intel.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
proc: enable writing to /proc/pid/mem

With recent changes there is no longer a security hazard with writing to
/proc/pid/mem.  Remove the #ifdef.

Signed-off-by: Stephen Wilson <wilsons@start.ca>
Signed-off-by: Al Viro <viro@zeniv.linux.org.uk>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>
lib: cpu_rmap: CPU affinity reverse-mapping

When initiating I/O on a multiqueue and multi-IRQ device, we may want
to select a queue for which the response will be handled on the same
or a nearby CPU.  This requires a reverse-map of IRQ affinity.  Add
library functions to support a generic reverse-mapping from CPUs to
objects with affinity and the specific case where the objects are
IRQs.

Signed-off-by: Ben Hutchings <bhutchings@solarflare.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
Signed-off-by: Nizar Lazuardy Firmansyah <nizar.digital@gmail.com>