What happens when you sleep

Once again a joy ride of a roller coaster that is the Linux kernel.

What happens when you sleep in the kernel. You here is the process context code that has either voluntarily relinquished the CPU or because it was doing a blocking call.

/**
   * mutex_lock - acquire the mutex
   * @lock: the mutex to be acquired
   *
   * Lock the mutex exclusively for this task. If the mutex is not
   * available right now, it will sleep until it can get it.
   *
   * The mutex must later on be released by the same task that
   * acquired it. Recursive locking is not allowed. The task
   * may not exit without first unlocking the mutex. Also, kernel
   * memory where the mutex resides must not be freed with
   * the mutex still locked. The mutex must first be initialized
   * (or statically defined) before it can be locked. memset()-ing
   * the mutex to 0 is not allowed.
   *
   * ( The CONFIG_DEBUG_MUTEXES .config option turns on debugging
   *   checks that will enforce the restrictions and will also do
   *   deadlock debugging. )
   *
   * This function is similar to (but not equivalent to) down().
   */
  void __sched mutex_lock(struct mutex *lock)
  {
        might_sleep();  //---> Just for Debugging.
        /*
         * The locking fastpath is the 1->0 transition from
        * 'unlocked' into 'locked' state.
        */
      __mutex_fastpath_lock(&lock->count, __mutex_lock_slowpath);
       mutex_set_owner(lock);
 }
 
 EXPORT_SYMBOL(mutex_lock);

Ingo Molnar's function header sums it up. 

Sorting method in Linux Kernel

I came across this source code lying in the kernel SRC, about a NON recursive sorting algorithm which does a pretty decent job at worst and average case scenarios.
The source file is /lib/sort.c
Prototype:void sort(void *base, size_t num, size_t size, int (*cmp_func)(const void *, const void *),          void (*swap_func)(void *, void *, int size))
This function does a heapsort on the given array. You may provide a
* swap_func function optimized to your element type.
* Sorting time is O(n log n) both on average and worst-case. While  qsort is about 20% faster on average, it suffers from exploitable O(n*n) worst-case behavior and extra memory requirements that make it less suitable for kernel use.
Heap sort is simple to implement, performs an O(n·lg(n)) in-place sort, but is not stable.
So our 1st task is to understand the HEAP DS.
A heap is a kind of binary tree having this property: every parent value is greater than (or equal to) its children's.
 The root always holds the max value
If the Parent value is less than its children, then the value is sifted down repeatedly until it proper heap is formed.
Suppose we have the following, arbitrarily assigned, array:



The right half side (the blue marked side) is already arranged as 
the bottom row of a heap, because its items have no children: 
consider, for instance the first 'blue' item, having value 24. 
Its index is 7, hence the heap properties for such item 
(h7>= h15, h7>= h16) are automatically satisfied, because there are no items with index 15 or 16 in the array.

So the 'blue side' is our partial heap and we can proceed with heap construction by repeatedly sifting down the items of the 'red side'.

3 - sifting down the first 'red' (left side) item of the array

The sift function would be implemented like this:
// The sift function:
// 'sifts down' the a[l] item until heap properties are restored
// ARGS:
//  a[] (INOUT) the array  (where a[l+1], a[l+2] .. a[size-1] is a partial heap)
//  size (IN) number of items of a
//  l (IN) index of the item inserted into the heap

void sift(int a[], int size, int l)
{
  int i,j, x;
  i = l;
  j = 2*i+1;
  x = a[i];
  while (j < size)
  {
    if ( j <size - 1)
      if ( a[j] < a[j+1])
        ++j;
    if (x >= a[j])
      break;
    a[i] = a[j];
    i = j;
    j = 2*i + 1; // sift
  }
  a[i] = x;
}

The creation of heap than becomes like this:

/ makes the heap using the R.W.Floyd's algorithm
// ARGS:
//  a[] (INOUT) the array wherein the heap is created
//  size (IN) the size of the array
 
void make_heap(int a[], int size)
{
  int l = size / 2;
  while (l)
  {
    --l;
    sift(a, size, l);
  }
} 

After all the operations are finished, We will get a heap array with
First element in array as Maximum value element in the unsorted 
array.

The 1st Fig: Unsorted Array. Fig2: Heaped array---> (29 is the max value).

so that the maximum value (29) is now the first item of the array (or, in other words, is on the top of the heap).

We can remove such maximum value (storing it in a safe place) and rearrange the remaining items in order to regain a heap (to obtain another 'maximum', that is the successive value of the sorted sequence).

It turns out the safe place for storing the maximum value is the last item of 
the array. As matter of fact, we swap the first and last item.

Now we have:

The maximum value in its own safe place (grayed, on the right side of the array)
A partial heap to fix (the blue items)
An item to sift down (the read one)

So We implement this heap_sort for arranging in descending order is:

void heapsort(int a[], int size)
{
  int l = 0, r = size;
  make_heap(a, size);
 
  while ( r > 1)
  {
    int tmp = a[0];
    --r;
    a[0] = a[r];
    a[r] = tmp;
    sift(a, r,0);
  }
}

NOTE: All credit for the diagrams and Source code for Heap sort goes to this guy:http://www.codeproject.com/Tips/732196/Heap-Data-Structure-and-Heap-Sort 

Now coming back to our kernel code for sort.c

void sort(void *base, size_t num, size_t size,
            int (*cmp_func)(const void *, const void *),
            void (*swap_func)(void *, void *, int size))
  {
          /* pre-scale counters for performance */
          int i = (num/2 - 1) * size, n = num * size, c, r;
  
          if (!swap_func) {
                  if (size == 4 && alignment_ok(base, 4))
                          swap_func = u32_swap;
                  else if (size == 8 && alignment_ok(base, 8))
                          swap_func = u64_swap;
                  else
                          swap_func = generic_swap;
          }
  
          /* heapify */
          for ( ; i >= 0; i -= size) {
                  for (r = i; r * 2 + size < n; r  = c) {
                          c = r * 2 + size;
                          if (c < n - size &&
                                          cmp_func(base + c, base + c + size) < 0)
                                  c += size;
                          if (cmp_func(base + r, base + c) >= 0)
                                  break;
                          swap_func(base + r, base + c, size);
                  }
          }
  
          /* sort */
          for (i = n - size; i > 0; i -= size) {
                  swap_func(base, base + i, size);
                  for (r = 0; r * 2 + size < i; r = c) {
                          c = r * 2 + size;
                          if (c < i - size &&
                                          cmp_func(base + c, base + c + size) < 0)
                                  c += size;
                          if (cmp_func(base + r, base + c) >= 0)
                                  break;
                          swap_func(base + r, base + c, size);
                  }
         }
 }