/*
 * Regression2
 * Description:
 * Toshiyuki Okajima describes the following radix-tree bug:
 *
 * In the following case, we can get a hangup on
 *   radix_radix_tree_gang_lookup_tag_slot.
 *
 * 0.  The radix tree contains RADIX_TREE_MAP_SIZE items. And the tag of
 *     a certain item has PAGECACHE_TAG_DIRTY.
 * 1.  radix_tree_range_tag_if_tagged(, start, end, , PAGECACHE_TAG_DIRTY,
 *     PAGECACHE_TAG_TOWRITE) is called to add PAGECACHE_TAG_TOWRITE tag
 *     for the tag which has PAGECACHE_TAG_DIRTY. However, there is no tag with
 *     PAGECACHE_TAG_DIRTY within the range from start to end. As the result,
 *     There is no tag with PAGECACHE_TAG_TOWRITE but the root tag has
 *     PAGECACHE_TAG_TOWRITE.
 * 2.  An item is added into the radix tree and then the level of it is
 *     extended into 2 from 1. At that time, the new radix tree node succeeds
 *     the tag status of the root tag. Therefore the tag of the new radix tree
 *     node has PAGECACHE_TAG_TOWRITE but there is not slot with
 *     PAGECACHE_TAG_TOWRITE tag in the child node of the new radix tree node.
 * 3.  The tag of a certain item is cleared with PAGECACHE_TAG_DIRTY.
 * 4.  All items within the index range from 0 to RADIX_TREE_MAP_SIZE - 1 are
 *     released. (Only the item which index is RADIX_TREE_MAP_SIZE exist in the
 *     radix tree.) As the result, the slot of the radix tree node is NULL but
 *     the tag which corresponds to the slot has PAGECACHE_TAG_TOWRITE.
 * 5.  radix_tree_gang_lookup_tag_slot(PAGECACHE_TAG_TOWRITE) calls
 *     __lookup_tag. __lookup_tag returns with 0. And __lookup_tag doesn't
 *     change the index that is the input and output parameter. Because the 1st
 *     slot of the radix tree node is NULL, but the tag which corresponds to
 *     the slot has PAGECACHE_TAG_TOWRITE.
 *     Therefore radix_tree_gang_lookup_tag_slot tries to get some items by
 *     calling __lookup_tag, but it cannot get any items forever.
 *
 * The fix is to change that radix_tree_tag_if_tagged doesn't tag the root tag
 * if it doesn't set any tags within the specified range.
 *
 * Running:
 * This test should run to completion immediately. The above bug would cause it
 * to hang indefinitely.
 *
 * Upstream commit:
 * Not yet
 */
#include <linux/kernel.h>
#include <linux/gfp.h>
#include <linux/slab.h>
#include <linux/radix-tree.h>
#include <stdlib.h>
#include <stdio.h>

#include "regression.h"
#include "test.h"

#define PAGECACHE_TAG_DIRTY     0
#define PAGECACHE_TAG_WRITEBACK 1
#define PAGECACHE_TAG_TOWRITE   2

static RADIX_TREE(mt_tree, GFP_KERNEL);
unsigned long page_count = 0;

struct page {
	unsigned long index;
};

static struct page *page_alloc(void)
{
	struct page *p;
	p = malloc(sizeof(struct page));
	p->index = page_count++;

	return p;
}

void regression2_test(void)
{
	int i;
	struct page *p;
	int max_slots = RADIX_TREE_MAP_SIZE;
	unsigned long int start, end;
	struct page *pages[1];

	printf("running regression test 2 (should take milliseconds)\n");
	/* 0. */
	for (i = 0; i <= max_slots - 1; i++) {
		p = page_alloc();
		radix_tree_insert(&mt_tree, i, p);
	}
	radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);

	/* 1. */
	start = 0;
	end = max_slots - 2;
	tag_tagged_items(&mt_tree, NULL, start, end, 1,
				PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE);

	/* 2. */
	p = page_alloc();
	radix_tree_insert(&mt_tree, max_slots, p);

	/* 3. */
	radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);

	/* 4. */
	for (i = max_slots - 1; i >= 0; i--)
		radix_tree_delete(&mt_tree, i);

	/* 5. */
	// NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot
	//       can return.
	start = 1;
	end = max_slots - 2;
	radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end,
		PAGECACHE_TAG_TOWRITE);

	/* We remove all the remained nodes */
	radix_tree_delete(&mt_tree, max_slots);

	printf("regression test 2, done\n");
}
value='0' selected='selected'>include</option><option value='1'>ignore</option></select></td></tr><tr><td class='label'>mode:</td><td class='ctrl'><select name='dt' onchange='this.form.submit();'><option value='0' selected='selected'>unified</option><option value='1'>ssdiff</option><option value='2'>stat only</option></select></td></tr><tr><td/><td class='ctrl'><noscript><input type='submit' value='reload'/></noscript></td></tr></table></form></div><table summary='commit info' class='commit-info'>
<tr><th>author</th><td>Jiri Slaby &lt;jslaby@suse.cz&gt;</td><td class='right'>2017-01-18 14:29:21 +0100</td></tr>
<tr><th>committer</th><td>Ingo Molnar &lt;mingo@kernel.org&gt;</td><td class='right'>2017-01-19 08:39:44 +0100</td></tr>
<tr><th>commit</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/dccp/feat.h?id=b5b46c4740aed1538544f0fa849c5b76c7823469'>b5b46c4740aed1538544f0fa849c5b76c7823469</a> (<a href='/cgit.cgi/linux/net-next.git/patch/net/dccp/feat.h?id=b5b46c4740aed1538544f0fa849c5b76c7823469'>patch</a>)</td></tr>
<tr><th>tree</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/tree/?id=b5b46c4740aed1538544f0fa849c5b76c7823469'>125e7aced4835bad6f6a0c0d02d012f333caf922</a> /<a href='/cgit.cgi/linux/net-next.git/tree/net/dccp/feat.h?id=b5b46c4740aed1538544f0fa849c5b76c7823469'>net/dccp/feat.h</a></td></tr>
<tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/dccp/feat.h?id=fa19a769f82fb9a5ca000b83cacd13fcaeda51ac'>fa19a769f82fb9a5ca000b83cacd13fcaeda51ac</a> (<a href='/cgit.cgi/linux/net-next.git/diff/net/dccp/feat.h?id=b5b46c4740aed1538544f0fa849c5b76c7823469&amp;id2=fa19a769f82fb9a5ca000b83cacd13fcaeda51ac'>diff</a>)</td></tr></table>
<div class='commit-subject'>objtool: Fix IRET's opcode</div><div class='commit-msg'>The IRET opcode is 0xcf according to the Intel manual and also to objdump of my
vmlinux:

    1ea8:       48 cf                   iretq

Fix the opcode in arch_decode_instruction().

The previous value (0xc5) seems to correspond to LDS.

Signed-off-by: Jiri Slaby &lt;jslaby@suse.cz&gt;
Acked-by: Josh Poimboeuf &lt;jpoimboe@redhat.com&gt;
Cc: Andy Lutomirski &lt;luto@kernel.org&gt;
Cc: Borislav Petkov &lt;bp@alien8.de&gt;
Cc: Brian Gerst &lt;brgerst@gmail.com&gt;
Cc: Denys Vlasenko &lt;dvlasenk@redhat.com&gt;
Cc: H. Peter Anvin &lt;hpa@zytor.com&gt;
Cc: Linus Torvalds &lt;torvalds@linux-foundation.org&gt;
Cc: Peter Zijlstra &lt;peterz@infradead.org&gt;
Cc: Thomas Gleixner &lt;tglx@linutronix.de&gt;
Link: http://lkml.kernel.org/r/20170118132921.19319-1-jslaby@suse.cz
Signed-off-by: Ingo Molnar &lt;mingo@kernel.org&gt;
</div><div class='diffstat-header'><a href='/cgit.cgi/linux/net-next.git/diff/?id=b5b46c4740aed1538544f0fa849c5b76c7823469'>Diffstat</a> (limited to 'net/dccp/feat.h')</div><table summary='diffstat' class='diffstat'>