Revision 1cbe06c3cf542d48eb22180163e00f91760ef8cd authored by Linus Torvalds on 28 May 2016, 18:04:16 UTC, committed by Linus Torvalds on 28 May 2016, 18:04:16 UTC
Pull more rdma updates from Doug Ledford: "This is the second group of code for the 4.7 merge window. It looks large, but only in one sense. I'll get to that in a minute. The list of changes here breaks down as follows: - Dynamic counter infrastructure in the IB drivers This is a sysfs based code to allow free form access to the hardware counters RDMA devices might support so drivers don't need to code this up repeatedly themselves - SendOnlyFullMember multicast support - IB router support - A couple misc fixes - The big item on the list: hfi1 driver updates, plus moving the hfi1 driver out of staging There was a group of 15 patches in the hfi1 list that I thought I had in the first pull request but they weren't. So that added to the length of the hfi1 section here. As far as these go, everything but the hfi1 is pretty straight forward. The hfi1 is, if you recall, the driver that Al had complaints about how it used the write/writev interfaces in an overloaded fashion. The write portion of their interface behaved like the write handler in the IB stack proper and did bi-directional communications. The writev interface, on the other hand, only accepts SDMA request structures. The completions for those structures are sent back via an entirely different event mechanism. With the security patch, we put security checks on the write interface, however, we also knew they would be going away soon. Now, we've converted the write handler in the hfi1 driver to use ioctls from the IB reserved magic area for its bidirectional communications. With that change, Intel has addressed all of the items originally on their TODO when they went into staging (as well as many items added to the list later). As such, I moved them out, and since they were the last item in the staging/rdma directory, and I don't have immediate plans to use the staging area again, I removed the staging/rdma area. Because of the move out of staging, as well as a series of 5 patches in the hfi1 driver that removed code people thought should be done in a different way and was optional to begin with (a snoop debug interface, an eeprom driver for an eeprom connected directory to their hfi1 chip and not via an i2c bus, and a few other things like that), the line count, especially the removal count, is high" * tag 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/dledford/rdma: (56 commits) staging/rdma: Remove the entire rdma subdirectory of staging IB/core: Make device counter infrastructure dynamic IB/hfi1: Fix pio map initialization IB/hfi1: Correct 8051 link parameter settings IB/hfi1: Update pkey table properly after link down or FM start IB/rdamvt: Fix rdmavt s_ack_queue sizing IB/rdmavt: Max atomic value should be a u8 IB/hfi1: Fix hard lockup due to not using save/restore spin lock IB/hfi1: Add tracing support for send with invalidate opcode IB/hfi1, qib: Add ieth to the packet header definitions IB/hfi1: Move driver out of staging IB/hfi1: Do not free hfi1 cdev parent structure early IB/hfi1: Add trace message in user IOCTL handling IB/hfi1: Remove write(), use ioctl() for user cmds IB/hfi1: Add ioctl() interface for user commands IB/hfi1: Remove unused user command IB/hfi1: Remove snoop/diag interface IB/hfi1: Remove EPROM functionality from data device IB/hfi1: Remove UI char device IB/hfi1: Remove multiple device cdev ...
list_sort.c
#define pr_fmt(fmt) "list_sort_test: " fmt
#include <linux/kernel.h>
#include <linux/bug.h>
#include <linux/compiler.h>
#include <linux/export.h>
#include <linux/string.h>
#include <linux/list_sort.h>
#include <linux/list.h>
#define MAX_LIST_LENGTH_BITS 20
/*
* Returns a list organized in an intermediate format suited
* to chaining of merge() calls: null-terminated, no reserved or
* sentinel head node, "prev" links not maintained.
*/
static struct list_head *merge(void *priv,
int (*cmp)(void *priv, struct list_head *a,
struct list_head *b),
struct list_head *a, struct list_head *b)
{
struct list_head head, *tail = &head;
while (a && b) {
/* if equal, take 'a' -- important for sort stability */
if ((*cmp)(priv, a, b) <= 0) {
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
tail->next = a?:b;
return head.next;
}
/*
* Combine final list merge with restoration of standard doubly-linked
* list structure. This approach duplicates code from merge(), but
* runs faster than the tidier alternatives of either a separate final
* prev-link restoration pass, or maintaining the prev links
* throughout.
*/
static void merge_and_restore_back_links(void *priv,
int (*cmp)(void *priv, struct list_head *a,
struct list_head *b),
struct list_head *head,
struct list_head *a, struct list_head *b)
{
struct list_head *tail = head;
u8 count = 0;
while (a && b) {
/* if equal, take 'a' -- important for sort stability */
if ((*cmp)(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
a = a->next;
} else {
tail->next = b;
b->prev = tail;
b = b->next;
}
tail = tail->next;
}
tail->next = a ? : b;
do {
/*
* In worst cases this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!(++count)))
(*cmp)(priv, tail->next, tail->next);
tail->next->prev = tail;
tail = tail->next;
} while (tail->next);
tail->next = head;
head->prev = tail;
}
/**
* list_sort - sort a list
* @priv: private data, opaque to list_sort(), passed to @cmp
* @head: the list to sort
* @cmp: the elements comparison function
*
* This function implements "merge sort", which has O(nlog(n))
* complexity.
*
* The comparison function @cmp must return a negative value if @a
* should sort before @b, and a positive value if @a should sort after
* @b. If @a and @b are equivalent, and their original relative
* ordering is to be preserved, @cmp must return 0.
*/
void list_sort(void *priv, struct list_head *head,
int (*cmp)(void *priv, struct list_head *a,
struct list_head *b))
{
struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
-- last slot is a sentinel */
int lev; /* index into part[] */
int max_lev = 0;
struct list_head *list;
if (list_empty(head))
return;
memset(part, 0, sizeof(part));
head->prev->next = NULL;
list = head->next;
while (list) {
struct list_head *cur = list;
list = list->next;
cur->next = NULL;
for (lev = 0; part[lev]; lev++) {
cur = merge(priv, cmp, part[lev], cur);
part[lev] = NULL;
}
if (lev > max_lev) {
if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
printk_once(KERN_DEBUG "list too long for efficiency\n");
lev--;
}
max_lev = lev;
}
part[lev] = cur;
}
for (lev = 0; lev < max_lev; lev++)
if (part[lev])
list = merge(priv, cmp, part[lev], list);
merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
}
EXPORT_SYMBOL(list_sort);
#ifdef CONFIG_TEST_LIST_SORT
#include <linux/slab.h>
#include <linux/random.h>
/*
* The pattern of set bits in the list length determines which cases
* are hit in list_sort().
*/
#define TEST_LIST_LEN (512+128+2) /* not including head */
#define TEST_POISON1 0xDEADBEEF
#define TEST_POISON2 0xA324354C
struct debug_el {
unsigned int poison1;
struct list_head list;
unsigned int poison2;
int value;
unsigned serial;
};
/* Array, containing pointers to all elements in the test list */
static struct debug_el **elts __initdata;
static int __init check(struct debug_el *ela, struct debug_el *elb)
{
if (ela->serial >= TEST_LIST_LEN) {
pr_err("error: incorrect serial %d\n", ela->serial);
return -EINVAL;
}
if (elb->serial >= TEST_LIST_LEN) {
pr_err("error: incorrect serial %d\n", elb->serial);
return -EINVAL;
}
if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
pr_err("error: phantom element\n");
return -EINVAL;
}
if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
pr_err("error: bad poison: %#x/%#x\n",
ela->poison1, ela->poison2);
return -EINVAL;
}
if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
pr_err("error: bad poison: %#x/%#x\n",
elb->poison1, elb->poison2);
return -EINVAL;
}
return 0;
}
static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
{
struct debug_el *ela, *elb;
ela = container_of(a, struct debug_el, list);
elb = container_of(b, struct debug_el, list);
check(ela, elb);
return ela->value - elb->value;
}
static int __init list_sort_test(void)
{
int i, count = 1, err = -ENOMEM;
struct debug_el *el;
struct list_head *cur;
LIST_HEAD(head);
pr_debug("start testing list_sort()\n");
elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
if (!elts) {
pr_err("error: cannot allocate memory\n");
return err;
}
for (i = 0; i < TEST_LIST_LEN; i++) {
el = kmalloc(sizeof(*el), GFP_KERNEL);
if (!el) {
pr_err("error: cannot allocate memory\n");
goto exit;
}
/* force some equivalencies */
el->value = prandom_u32() % (TEST_LIST_LEN / 3);
el->serial = i;
el->poison1 = TEST_POISON1;
el->poison2 = TEST_POISON2;
elts[i] = el;
list_add_tail(&el->list, &head);
}
list_sort(NULL, &head, cmp);
err = -EINVAL;
for (cur = head.next; cur->next != &head; cur = cur->next) {
struct debug_el *el1;
int cmp_result;
if (cur->next->prev != cur) {
pr_err("error: list is corrupted\n");
goto exit;
}
cmp_result = cmp(NULL, cur, cur->next);
if (cmp_result > 0) {
pr_err("error: list is not sorted\n");
goto exit;
}
el = container_of(cur, struct debug_el, list);
el1 = container_of(cur->next, struct debug_el, list);
if (cmp_result == 0 && el->serial >= el1->serial) {
pr_err("error: order of equivalent elements not "
"preserved\n");
goto exit;
}
if (check(el, el1)) {
pr_err("error: element check failed\n");
goto exit;
}
count++;
}
if (head.prev != cur) {
pr_err("error: list is corrupted\n");
goto exit;
}
if (count != TEST_LIST_LEN) {
pr_err("error: bad list length %d", count);
goto exit;
}
err = 0;
exit:
for (i = 0; i < TEST_LIST_LEN; i++)
kfree(elts[i]);
kfree(elts);
return err;
}
late_initcall(list_sort_test);
#endif /* CONFIG_TEST_LIST_SORT */
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...