litmus-rt-tegra.git - LITMUS^RT and MC^2 V0 support for the NVIDIA Tegra 3 SoC

about summary refs log tree commit diff stats

diff options

author	Jonathan Herman <hermanjl@cs.unc.edu>	2013-01-22 10:38:37 -0500
committer	Jonathan Herman <hermanjl@cs.unc.edu>	2013-01-22 10:38:37 -0500
commit	fcc9d2e5a6c89d22b8b773a64fb4ad21ac318446 (patch)
tree	a57612d1888735a2ec7972891b68c1ac5ec8faea /drivers/video/console
parent	8dea78da5cee153b8af9c07a2745f6c55057fe12 (diff)

Added missing tegra files.HEAD master

Diffstat (limited to 'drivers/video/console')

0 files changed, 0 insertions, 0 deletions

re>1da177e4c3f4

51
52
53

60
61

62
63

71
72

75
76

77
78
79

81
82

83
84

98
99

105
106

133
134

135
136

141
142

147
148
149

150
151

163
164

165
166

167
168

177
178

184
185
186

199
200

203
204

210
211

213
214

223
224

228
229

231
232
233

241
242

248
249
250

252
253

261
262

267
268

272
273

274
275

276
277

280
281

282
283

292
293

295
296

304
305

310
311

315
316

317
318

319
320

323
324

325
326

332
333
334

335
336

338
339

341
342

343
344

346
347

348
349
350

351
352

353
354

371
372

376
377

380
381

390
391

407
408

415
416

423
424

435
436

442
443

449
450

455
456
457

458
459
460

463
464

465
466

478
479

480
481

483
484
485

486
487

488
489

491
492

493
494

499
500

501
502

506
507

515
516

517
518

558
559

586
587

602
603
604

607
608

626
627

628
629

632
633

636
637

639
640
641

643
644
645

648
649

651
652

661
662

663
664

665
666
667

669
670
671

672
673

685
686

688
689
690

693
694
695

705
706

707
708

716
717

718
719

725
726

740
741

743
744

761
762

767
768

787
788
789

792
793

813
814
815

830
831
832

834
835

836
837

841
842

847
848

849
850

858
859

861
862

867
868

871
872
873

875
876

878
879
880

881
882

899
900

911
912
913

943
944

949
950

979
980

989
990

992
993

997
998

1004
1005

1007
1008

1013
1014

1017
1018
1019

1028
1029

1036
1037
1038

1042
1043

1045
1046
1047

1048
1049

1059
1060

1072
1073

1074
1075

1086
1087

1096
1097
1098

1107
1108

1121
1122

1131
1132
1133

1134
1135
1136

1144
1145

1173
1174
1175

1193
1194

1195
1196

1197
1198

1206
1207

1208
1209

1212
1213

1221
1222

1223
1224

1226
1227

1236
1237
1238

1256
1257

1258
1259
1260

1284
1285
1286

1288
1289

1294
1295

1296
1297

1306
1307

1325
1326

1343
1344
1345

1359
1360

1377
1378
1379

1397
1398

1400
1401

1402
1403

1423
1424

1428
1429

1461
1462

1466
1467

1472
1473

1480
1481
1482

1488
1489

1490
1491

1518
1519

1536
1537
1538

1539
1540

1541
1542

1545
1546

1580
1581
1582

1583
1584

1586
1587

1591
1592

1597
1598
1599

1600
1601

1607
1608

1622
1623
1624

1627
1628
1629

1632
1633

1634
1635

1647
1648
1649

1650
1651

1652
1653

1659
1660

1662
1663
1664

1666
1667
1668

1671
1672

1684
1685

1688
1689
1690

1701
1702

1705
1706
1707

1712
1713

1721
1722

1738
1739

1740
1741

1743
1744

1753
1754

1755
1756

1757
1758

1769
1770
1771

1777
1778

1779
1780

1784
1785

1796
1797

1799
1800

1806
1807

1819
1820
1821

1834
1835

1838
1839

1842
1843
1844

1847
1848

1851
1852
1853

1864
1865
1866

1873
1874

1877
1878

1879
1880

1885
1886

1889
1890

1895
1896

1904
1905

1913
1914
1915

1926
1927
1928

1929
1930
1931

1939
1940

1941
1942
1943

1948
1949

1950
1951

1963
1964

1965
1966

1969
1970

1971
1972

1980
1981

1982
1983
1984

1986
1987
1988

1994
1995

2001
2002

2004
2005
2006

2012
2013
2014

2023
2024

2030
2031

2060
2061

2064
2065

2066
2067

2072
2073

2077
2078
2079

2081
2082

2083
2084

2085
2086
2087

2102
2103

2105
2106

2113
2114

/*
 *  Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 */

/*
 *  Written by Anatoly P. Pinchuk pap@namesys.botik.ru
 *  Programm System Institute
 *  Pereslavl-Zalessky Russia
 */

/*
 *  This file contains functions dealing with S+tree
 *
 * B_IS_IN_TREE
 * copy_item_head
 * comp_short_keys
 * comp_keys
 * comp_short_le_keys
 * le_key2cpu_key
 * comp_le_keys
 * bin_search
 * get_lkey
 * get_rkey
 * key_in_buffer
 * decrement_bcount
 * reiserfs_check_path
 * pathrelse_and_restore
 * pathrelse
 * search_by_key_reada
 * search_by_key
 * search_for_position_by_key
 * comp_items
 * prepare_for_direct_item
 * prepare_for_direntry_item
 * prepare_for_delete_or_cut
 * calc_deleted_bytes_number
 * init_tb_struct
 * padd_item
 * reiserfs_delete_item
 * reiserfs_delete_solid_item
 * reiserfs_delete_object
 * maybe_indirect_to_direct
 * indirect_to_direct_roll_back
 * reiserfs_cut_from_item
 * truncate_directory
 * reiserfs_do_truncate
 * reiserfs_paste_into_item
 * reiserfs_insert_item
 */

#include <linux/time.h>
#include <linux/string.h>
#include <linux/pagemap.h>
#include "reiserfs.h"
#include <linux/buffer_head.h>
#include <linux/quotaops.h>

/* Does the buffer contain a disk block which is in the tree. */
inline int B_IS_IN_TREE(const struct buffer_head *bh)
{

	RFALSE(B_LEVEL(bh) > MAX_HEIGHT,
	       "PAP-1010: block (%b) has too big level (%z)", bh, bh);

	return (B_LEVEL(bh) != FREE_LEVEL);
}

//
// to gets item head in le form
//
inline void copy_item_head(struct item_head *to,
			   const struct item_head *from)
{
	memcpy(to, from, IH_SIZE);
}

/* k1 is pointer to on-disk structure which is stored in little-endian
   form. k2 is pointer to cpu variable. For key of items of the same
   object this returns 0.
   Returns: -1 if key1 < key2
   0 if key1 == key2
   1 if key1 > key2 */
inline int comp_short_keys(const struct reiserfs_key *le_key,
			   const struct cpu_key *cpu_key)
{
	__u32 n;
	n = le32_to_cpu(le_key->k_dir_id);
	if (n < cpu_key->on_disk_key.k_dir_id)
		return -1;
	if (n > cpu_key->on_disk_key.k_dir_id)
		return 1;
	n = le32_to_cpu(le_key->k_objectid);
	if (n < cpu_key->on_disk_key.k_objectid)
		return -1;
	if (n > cpu_key->on_disk_key.k_objectid)
		return 1;
	return 0;
}

/* k1 is pointer to on-disk structure which is stored in little-endian
   form. k2 is pointer to cpu variable.
   Compare keys using all 4 key fields.
   Returns: -1 if key1 < key2 0
   if key1 = key2 1 if key1 > key2 */
static inline int comp_keys(const struct reiserfs_key *le_key,
			    const struct cpu_key *cpu_key)
{
	int retval;

	retval = comp_short_keys(le_key, cpu_key);
	if (retval)
		return retval;
	if (le_key_k_offset(le_key_version(le_key), le_key) <
	    cpu_key_k_offset(cpu_key))
		return -1;
	if (le_key_k_offset(le_key_version(le_key), le_key) >
	    cpu_key_k_offset(cpu_key))
		return 1;

	if (cpu_key->key_length == 3)
		return 0;

	/* this part is needed only when tail conversion is in progress */
	if (le_key_k_type(le_key_version(le_key), le_key) <
	    cpu_key_k_type(cpu_key))
		return -1;

	if (le_key_k_type(le_key_version(le_key), le_key) >
	    cpu_key_k_type(cpu_key))
		return 1;

	return 0;
}

inline int comp_short_le_keys(const struct reiserfs_key *key1,
			      const struct reiserfs_key *key2)
{
	__u32 *k1_u32, *k2_u32;
	int key_length = REISERFS_SHORT_KEY_LEN;

	k1_u32 = (__u32 *) key1;
	k2_u32 = (__u32 *) key2;
	for (; key_length--; ++k1_u32, ++k2_u32) {
		if (le32_to_cpu(*k1_u32) < le32_to_cpu(*k2_u32))
			return -1;
		if (le32_to_cpu(*k1_u32) > le32_to_cpu(*k2_u32))
			return 1;
	}
	return 0;
}

inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from)
{
	int version;
	to->on_disk_key.k_dir_id = le32_to_cpu(from->k_dir_id);
	to->on_disk_key.k_objectid = le32_to_cpu(from->k_objectid);

	// find out version of the key
	version = le_key_version(from);
	to->version = version;
	to->on_disk_key.k_offset = le_key_k_offset(version, from);
	to->on_disk_key.k_type = le_key_k_type(version, from);
}

// this does not say which one is bigger, it only returns 1 if keys
// are not equal, 0 otherwise
inline int comp_le_keys(const struct reiserfs_key *k1,
			const struct reiserfs_key *k2)
{
	return memcmp(k1, k2, sizeof(struct reiserfs_key));
}

/**************************************************************************
 *  Binary search toolkit function                                        *
 *  Search for an item in the array by the item key                       *
 *  Returns:    1 if found,  0 if not found;                              *
 *        *pos = number of the searched element if found, else the        *
 *        number of the first element that is larger than key.            *
 **************************************************************************/
/* For those not familiar with binary search: lbound is the leftmost item that it
 could be, rbound the rightmost item that it could be.  We examine the item
 halfway between lbound and rbound, and that tells us either that we can increase
 lbound, or decrease rbound, or that we have found it, or if lbound <= rbound that
 there are no possible items, and we have not found it. With each examination we
 cut the number of possible items it could be by one more than half rounded down,
 or we find it. */
static inline int bin_search(const void *key,	/* Key to search for. */
			     const void *base,	/* First item in the array. */
			     int num,	/* Number of items in the array. */
			     int width,	/* Item size in the array.
					   searched. Lest the reader be
					   confused, note that this is crafted
					   as a general function, and when it
					   is applied specifically to the array
					   of item headers in a node, width
					   is actually the item header size not
					   the item size. */
			     int *pos /* Number of the searched for element. */
    )
{
	int rbound, lbound, j;

	for (j = ((rbound = num - 1) + (lbound = 0)) / 2;
	     lbound <= rbound; j = (rbound + lbound) / 2)
		switch (comp_keys
			((struct reiserfs_key *)((char *)base + j * width),
			 (struct cpu_key *)key)) {
		case -1:
			lbound = j + 1;
			continue;
		case 1:
			rbound = j - 1;
			continue;
		case 0:
			*pos = j;
			return ITEM_FOUND;	/* Key found in the array.  */
		}

	/* bin_search did not find given key, it returns position of key,
	   that is minimal and greater than the given one. */
	*pos = lbound;
	return ITEM_NOT_FOUND;
}


/* Minimal possible key. It is never in the tree. */
const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} };

/* Maximal possible key. It is never in the tree. */
static const struct reiserfs_key MAX_KEY = {
	__constant_cpu_to_le32(0xffffffff),
	__constant_cpu_to_le32(0xffffffff),
	{{__constant_cpu_to_le32(0xffffffff),
	  __constant_cpu_to_le32(0xffffffff)},}
};

/* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom
   of the path, and going upwards.  We must check the path's validity at each step.  If the key is not in
   the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this
   case we return a special key, either MIN_KEY or MAX_KEY. */
static inline const struct reiserfs_key *get_lkey(const struct treepath *chk_path,
						  const struct super_block *sb)
{
	int position, path_offset = chk_path->path_length;
	struct buffer_head *parent;

	RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET,
	       "PAP-5010: invalid offset in the path");

	/* While not higher in path than first element. */
	while (path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {

		RFALSE(!buffer_uptodate
		       (PATH_OFFSET_PBUFFER(chk_path, path_offset)),
		       "PAP-5020: parent is not uptodate");

		/* Parent at the path is not in the tree now. */
		if (!B_IS_IN_TREE
		    (parent =
		     PATH_OFFSET_PBUFFER(chk_path, path_offset)))
			return &MAX_KEY;
		/* Check whether position in the parent is correct. */
		if ((position =
		     PATH_OFFSET_POSITION(chk_path,
					  path_offset)) >
		    B_NR_ITEMS(parent))
			return &MAX_KEY;
		/* Check whether parent at the path really points to the child. */
		if (B_N_CHILD_NUM(parent, position) !=
		    PATH_OFFSET_PBUFFER(chk_path,
					path_offset + 1)->b_blocknr)
			return &MAX_KEY;
		/* Return delimiting key if position in the parent is not equal to zero. */
		if (position)
			return B_N_PDELIM_KEY(parent, position - 1);
	}
	/* Return MIN_KEY if we are in the root of the buffer tree. */
	if (PATH_OFFSET_PBUFFER(chk_path, FIRST_PATH_ELEMENT_OFFSET)->
	    b_blocknr == SB_ROOT_BLOCK(sb))
		return &MIN_KEY;
	return &MAX_KEY;
}

/* Get delimiting key of the buffer at the path and its right neighbor. */
inline const struct reiserfs_key *get_rkey(const struct treepath *chk_path,
					   const struct super_block *sb)
{
	int position, path_offset = chk_path->path_length;
	struct buffer_head *parent;

	RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET,
	       "PAP-5030: invalid offset in the path");

	while (path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {

		RFALSE(!buffer_uptodate
		       (PATH_OFFSET_PBUFFER(chk_path, path_offset)),
		       "PAP-5040: parent is not uptodate");

		/* Parent at the path is not in the tree now. */
		if (!B_IS_IN_TREE
		    (parent =
		     PATH_OFFSET_PBUFFER(chk_path, path_offset)))
			return &MIN_KEY;
		/* Check whether position in the parent is correct. */
		if ((position =
		     PATH_OFFSET_POSITION(chk_path,
					  path_offset)) >
		    B_NR_ITEMS(parent))
			return &MIN_KEY;
		/* Check whether parent at the path really points to the child. */
		if (B_N_CHILD_NUM(parent, position) !=
		    PATH_OFFSET_PBUFFER(chk_path,
					path_offset + 1)->b_blocknr)
			return &MIN_KEY;
		/* Return delimiting key if position in the parent is not the last one. */
		if (position != B_NR_ITEMS(parent))
			return B_N_PDELIM_KEY(parent, position);
	}
	/* Return MAX_KEY if we are in the root of the buffer tree. */
	if (PATH_OFFSET_PBUFFER(chk_path, FIRST_PATH_ELEMENT_OFFSET)->
	    b_blocknr == SB_ROOT_BLOCK(sb))
		return &MAX_KEY;
	return &MIN_KEY;
}

/* Check whether a key is contained in the tree rooted from a buffer at a path. */
/* This works by looking at the left and right delimiting keys for the buffer in the last path_element in
   the path.  These delimiting keys are stored at least one level above that buffer in the tree. If the
   buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in
   this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */
static inline int key_in_buffer(struct treepath *chk_path,	/* Path which should be checked.  */
				const struct cpu_key *key,	/* Key which should be checked.   */
				struct super_block *sb
    )
{

	RFALSE(!key || chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET
	       || chk_path->path_length > MAX_HEIGHT,
	       "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)",
	       key, chk_path->path_length);
	RFALSE(!PATH_PLAST_BUFFER(chk_path)->b_bdev,
	       "PAP-5060: device must not be NODEV");

	if (comp_keys(get_lkey(chk_path, sb), key) == 1)
		/* left delimiting key is bigger, that the key we look for */
		return 0;
	/*  if ( comp_keys(key, get_rkey(chk_path, sb)) != -1 ) */
	if (comp_keys(get_rkey(chk_path, sb), key) != 1)
		/* key must be less than right delimitiing key */
		return 0;
	return 1;
}

int reiserfs_check_path(struct treepath *p)
{
	RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET,
	       "path not properly relsed");
	return 0;
}

/* Drop the reference to each buffer in a path and restore
 * dirty bits clean when preparing the buffer for the log.
 * This version should only be called from fix_nodes() */
void pathrelse_and_restore(struct super_block *sb,
			   struct treepath *search_path)
{
	int path_offset = search_path->path_length;

	RFALSE(path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
	       "clm-4000: invalid path offset");

	while (path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
		struct buffer_head *bh;
		bh = PATH_OFFSET_PBUFFER(search_path, path_offset--);
		reiserfs_restore_prepared_buffer(sb, bh);
		brelse(bh);
	}
	search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
}

/* Drop the reference to each buffer in a path */
void pathrelse(struct treepath *search_path)
{
	int path_offset = search_path->path_length;

	RFALSE(path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
	       "PAP-5090: invalid path offset");

	while (path_offset > ILLEGAL_PATH_ELEMENT_OFFSET)
		brelse(PATH_OFFSET_PBUFFER(search_path, path_offset--));

	search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
}

static int is_leaf(char *buf, int blocksize, struct buffer_head *bh)
{
	struct block_head *blkh;
	struct item_head *ih;
	int used_space;
	int prev_location;
	int i;
	int nr;

	blkh = (struct block_head *)buf;
	if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) {
		reiserfs_warning(NULL, "reiserfs-5080",
				 "this should be caught earlier");
		return 0;
	}

	nr = blkh_nr_item(blkh);
	if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) {
		/* item number is too big or too small */
		reiserfs_warning(NULL, "reiserfs-5081",
				 "nr_item seems wrong: %z", bh);
		return 0;
	}
	ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
	used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih));
	if (used_space != blocksize - blkh_free_space(blkh)) {
		/* free space does not match to calculated amount of use space */
		reiserfs_warning(NULL, "reiserfs-5082",
				 "free space seems wrong: %z", bh);
		return 0;
	}
	// FIXME: it is_leaf will hit performance too much - we may have
	// return 1 here

	/* check tables of item heads */
	ih = (struct item_head *)(buf + BLKH_SIZE);
	prev_location = blocksize;
	for (i = 0; i < nr; i++, ih++) {
		if (le_ih_k_type(ih) == TYPE_ANY) {
			reiserfs_warning(NULL, "reiserfs-5083",
					 "wrong item type for item %h",
					 ih);
			return 0;
		}
		if (ih_location(ih) >= blocksize
		    || ih_location(ih) < IH_SIZE * nr) {
			reiserfs_warning(NULL, "reiserfs-5084",
					 "item location seems wrong: %h",
					 ih);
			return 0;
		}
		if (ih_item_len(ih) < 1
		    || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) {
			reiserfs_warning(NULL, "reiserfs-5085",
					 "item length seems wrong: %h",
					 ih);
			return 0;
		}
		if (prev_location - ih_location(ih) != ih_item_len(ih)) {
			reiserfs_warning(NULL, "reiserfs-5086",
					 "item location seems wrong "
					 "(second one): %h", ih);
			return 0;
		}
		prev_location = ih_location(ih);
	}

	// one may imagine much more checks
	return 1;
}

/* returns 1 if buf looks like an internal node, 0 otherwise */
static int is_internal(char *buf, int blocksize, struct buffer_head *bh)
{
	struct block_head *blkh;
	int nr;
	int used_space;

	blkh = (struct block_head *)buf;
	nr = blkh_level(blkh);
	if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) {
		/* this level is not possible for internal nodes */
		reiserfs_warning(NULL, "reiserfs-5087",
				 "this should be caught earlier");
		return 0;
	}

	nr = blkh_nr_item(blkh);
	if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) {
		/* for internal which is not root we might check min number of keys */
		reiserfs_warning(NULL, "reiserfs-5088",
				 "number of key seems wrong: %z", bh);
		return 0;
	}

	used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
	if (used_space != blocksize - blkh_free_space(blkh)) {
		reiserfs_warning(NULL, "reiserfs-5089",
				 "free space seems wrong: %z", bh);
		return 0;
	}
	// one may imagine much more checks
	return 1;
}

// make sure that bh contains formatted node of reiserfs tree of
// 'level'-th level
static int is_tree_node(struct buffer_head *bh, int level)
{
	if (B_LEVEL(bh) != level) {
		reiserfs_warning(NULL, "reiserfs-5090", "node level %d does "
				 "not match to the expected one %d",
				 B_LEVEL(bh), level);
		return 0;
	}
	if (level == DISK_LEAF_NODE_LEVEL)
		return is_leaf(bh->b_data, bh->b_size, bh);

	return is_internal(bh->b_data, bh->b_size, bh);
}

#define SEARCH_BY_KEY_READA 16

/*
 * The function is NOT SCHEDULE-SAFE!
 * It might unlock the write lock if we needed to wait for a block
 * to be read. Note that in this case it won't recover the lock to avoid
 * high contention resulting from too much lock requests, especially
 * the caller (search_by_key) will perform other schedule-unsafe
 * operations just after calling this function.
 *
 * @return true if we have unlocked
 */
static bool search_by_key_reada(struct super_block *s,
				struct buffer_head **bh,
				b_blocknr_t *b, int num)
{
	int i, j;
	bool unlocked = false;

	for (i = 0; i < num; i++) {
		bh[i] = sb_getblk(s, b[i]);
	}
	/*
	 * We are going to read some blocks on which we
	 * have a reference. It's safe, though we might be
	 * reading blocks concurrently changed if we release
	 * the lock. But it's still fine because we check later
	 * if the tree changed
	 */
	for (j = 0; j < i; j++) {
		/*
		 * note, this needs attention if we are getting rid of the BKL
		 * you have to make sure the prepared bit isn't set on this buffer
		 */
		if (!buffer_uptodate(bh[j])) {
			if (!unlocked) {
				reiserfs_write_unlock(s);
				unlocked = true;
			}
			ll_rw_block(READA, 1, bh + j);
		}
		brelse(bh[j]);
	}
	return unlocked;
}

/**************************************************************************
 * Algorithm   SearchByKey                                                *
 *             look for item in the Disk S+Tree by its key                *
 * Input:  sb   -  super block                                            *
 *         key  - pointer to the key to search                            *
 * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR                         *
 *         search_path - path from the root to the needed leaf            *
 **************************************************************************/

/* This function fills up the path from the root to the leaf as it
   descends the tree looking for the key.  It uses reiserfs_bread to
   try to find buffers in the cache given their block number.  If it
   does not find them in the cache it reads them from disk.  For each
   node search_by_key finds using reiserfs_bread it then uses
   bin_search to look through that node.  bin_search will find the
   position of the block_number of the next node if it is looking
   through an internal node.  If it is looking through a leaf node
   bin_search will find the position of the item which has key either
   equal to given key, or which is the maximal key less than the given
   key.  search_by_key returns a path that must be checked for the
   correctness of the top of the path but need not be checked for the
   correctness of the bottom of the path */
/* The function is NOT SCHEDULE-SAFE! */
int search_by_key(struct super_block *sb, const struct cpu_key *key,	/* Key to search. */
		  struct treepath *search_path,/* This structure was
						   allocated and initialized
						   by the calling
						   function. It is filled up
						   by this function.  */
		  int stop_level	/* How far down the tree to search. To
					   stop at leaf level - set to
					   DISK_LEAF_NODE_LEVEL */
    )
{
	b_blocknr_t block_number;
	int expected_level;
	struct buffer_head *bh;
	struct path_element *last_element;
	int node_level, retval;
	int right_neighbor_of_leaf_node;
	int fs_gen;
	struct buffer_head *reada_bh[SEARCH_BY_KEY_READA];
	b_blocknr_t reada_blocks[SEARCH_BY_KEY_READA];
	int reada_count = 0;

#ifdef CONFIG_REISERFS_CHECK
	int repeat_counter = 0;
#endif

	PROC_INFO_INC(sb, search_by_key);

	/* As we add each node to a path we increase its count.  This means that
	   we must be careful to release all nodes in a path before we either
	   discard the path struct or re-use the path struct, as we do here. */

	pathrelse(search_path);

	right_neighbor_of_leaf_node = 0;

	/* With each iteration of this loop we search through the items in the
	   current node, and calculate the next current node(next path element)
	   for the next iteration of this loop.. */
	block_number = SB_ROOT_BLOCK(sb);
	expected_level = -1;
	while (1) {

#ifdef CONFIG_REISERFS_CHECK
		if (!(++repeat_counter % 50000))
			reiserfs_warning(sb, "PAP-5100",
					 "%s: there were %d iterations of "
					 "while loop looking for key %K",
					 current->comm, repeat_counter,
					 key);
#endif

		/* prep path to have another element added to it. */
		last_element =
		    PATH_OFFSET_PELEMENT(search_path,
					 ++search_path->path_length);
		fs_gen = get_generation(sb);

		/* Read the next tree node, and set the last element in the path to
		   have a pointer to it. */
		if ((bh = last_element->pe_buffer =
		     sb_getblk(sb, block_number))) {
			bool unlocked = false;

			if (!buffer_uptodate(bh) && reada_count > 1)
				/* may unlock the write lock */
				unlocked = search_by_key_reada(sb, reada_bh,
						    reada_blocks, reada_count);
			/*
			 * If we haven't already unlocked the write lock,
			 * then we need to do that here before reading
			 * the current block
			 */
			if (!buffer_uptodate(bh) && !unlocked) {
				reiserfs_write_unlock(sb);
				unlocked = true;
			}
			ll_rw_block(READ, 1, &bh);
			wait_on_buffer(bh);

			if (unlocked)
				reiserfs_write_lock(sb);
			if (!buffer_uptodate(bh))
				goto io_error;
		} else {
		      io_error:
			search_path->path_length--;
			pathrelse(search_path);
			return IO_ERROR;
		}
		reada_count = 0;
		if (expected_level == -1)
			expected_level = SB_TREE_HEIGHT(sb);
		expected_level--;

		/* It is possible that schedule occurred. We must check whether the key
		   to search is still in the tree rooted from the current buffer. If
		   not then repeat search from the root. */
		if (fs_changed(fs_gen, sb) &&
		    (!B_IS_IN_TREE(bh) ||
		     B_LEVEL(bh) != expected_level ||
		     !key_in_buffer(search_path, key, sb))) {
			PROC_INFO_INC(sb, search_by_key_fs_changed);
			PROC_INFO_INC(sb, search_by_key_restarted);
			PROC_INFO_INC(sb,
				      sbk_restarted[expected_level - 1]);
			pathrelse(search_path);

			/* Get the root block number so that we can repeat the search
			   starting from the root. */
			block_number = SB_ROOT_BLOCK(sb);
			expected_level = -1;
			right_neighbor_of_leaf_node = 0;

			/* repeat search from the root */
			continue;
		}

		/* only check that the key is in the buffer if key is not
		   equal to the MAX_KEY. Latter case is only possible in
		   "finish_unfinished()" processing during mount. */
		RFALSE(comp_keys(&MAX_KEY, key) &&
		       !key_in_buffer(search_path, key, sb),
		       "PAP-5130: key is not in the buffer");
#ifdef CONFIG_REISERFS_CHECK
		if (REISERFS_SB(sb)->cur_tb) {
			print_cur_tb("5140");
			reiserfs_panic(sb, "PAP-5140",
				       "schedule occurred in do_balance!");
		}
#endif

		// make sure, that the node contents look like a node of
		// certain level
		if (!is_tree_node(bh, expected_level)) {
			reiserfs_error(sb, "vs-5150",
				       "invalid format found in block %ld. "
				       "Fsck?", bh->b_blocknr);
			pathrelse(search_path);
			return IO_ERROR;
		}

		/* ok, we have acquired next formatted node in the tree */
		node_level = B_LEVEL(bh);

		PROC_INFO_BH_STAT(sb, bh, node_level - 1);

		RFALSE(node_level < stop_level,
		       "vs-5152: tree level (%d) is less than stop level (%d)",
		       node_level, stop_level);

		retval = bin_search(key, B_N_PITEM_HEAD(bh, 0),
				      B_NR_ITEMS(bh),
				      (node_level ==
				       DISK_LEAF_NODE_LEVEL) ? IH_SIZE :
				      KEY_SIZE,
				      &(last_element->pe_position));
		if (node_level == stop_level) {
			return retval;
		}

		/* we are not in the stop level */
		if (retval == ITEM_FOUND)
			/* item has been found, so we choose the pointer which is to the right of the found one */
			last_element->pe_position++;

		/* if item was not found we choose the position which is to
		   the left of the found item. This requires no code,
		   bin_search did it already. */

		/* So we have chosen a position in the current node which is
		   an internal node.  Now we calculate child block number by
		   position in the node. */
		block_number =
		    B_N_CHILD_NUM(bh, last_element->pe_position);

		/* if we are going to read leaf nodes, try for read ahead as well */
		if ((search_path->reada & PATH_READA) &&
		    node_level == DISK_LEAF_NODE_LEVEL + 1) {
			int pos = last_element->pe_position;
			int limit = B_NR_ITEMS(bh);
			struct reiserfs_key *le_key;

			if (search_path->reada & PATH_READA_BACK)
				limit = 0;
			while (reada_count < SEARCH_BY_KEY_READA) {
				if (pos == limit)
					break;
				reada_blocks[reada_count++] =
				    B_N_CHILD_NUM(bh, pos);
				if (search_path->reada & PATH_READA_BACK)
					pos--;
				else
					pos++;

				/*
				 * check to make sure we're in the same object
				 */
				le_key = B_N_PDELIM_KEY(bh, pos);
				if (le32_to_cpu(le_key->k_objectid) !=
				    key->on_disk_key.k_objectid) {
					break;
				}
			}
		}
	}
}

/* Form the path to an item and position in this item which contains
   file byte defined by key. If there is no such item
   corresponding to the key, we point the path to the item with
   maximal key less than key, and *pos_in_item is set to one
   past the last entry/byte in the item.  If searching for entry in a
   directory item, and it is not found, *pos_in_item is set to one
   entry more than the entry with maximal key which is less than the
   sought key.

   Note that if there is no entry in this same node which is one more,
   then we point to an imaginary entry.  for direct items, the
   position is in units of bytes, for indirect items the position is
   in units of blocknr entries, for directory items the position is in
   units of directory entries.  */

/* The function is NOT SCHEDULE-SAFE! */
int search_for_position_by_key(struct super_block *sb,	/* Pointer to the super block.          */
			       const struct cpu_key *p_cpu_key,	/* Key to search (cpu variable)         */
			       struct treepath *search_path	/* Filled up by this function.          */
    )
{


context:
space:
mode: