1	// SPDX-License-Identifier: GPL-2.0-only
2	/*
3	* Copyright (C) Sistina Software, Inc. 1997-2003 All rights reserved.
4	* Copyright (C) 2004-2006 Red Hat, Inc. All rights reserved.
5	*/
6
7	/*
8	* Implements Extendible Hashing as described in:
9	* "Extendible Hashing" by Fagin, et al in
10	* __ACM Trans. on Database Systems__, Sept 1979.
11	*
12	*
13	* Here's the layout of dirents which is essentially the same as that of ext2
14	* within a single block. The field de_name_len is the number of bytes
15	* actually required for the name (no null terminator). The field de_rec_len
16	* is the number of bytes allocated to the dirent. The offset of the next
17	* dirent in the block is (dirent + dirent->de_rec_len). When a dirent is
18	* deleted, the preceding dirent inherits its allocated space, ie
19	* prev->de_rec_len += deleted->de_rec_len. Since the next dirent is obtained
20	* by adding de_rec_len to the current dirent, this essentially causes the
21	* deleted dirent to get jumped over when iterating through all the dirents.
22	*
23	* When deleting the first dirent in a block, there is no previous dirent so
24	* the field de_ino is set to zero to designate it as deleted. When allocating
25	* a dirent, gfs2_dirent_alloc iterates through the dirents in a block. If the
26	* first dirent has (de_ino == 0) and de_rec_len is large enough, this first
27	* dirent is allocated. Otherwise it must go through all the 'used' dirents
28	* searching for one in which the amount of total space minus the amount of
29	* used space will provide enough space for the new dirent.
30	*
31	* There are two types of blocks in which dirents reside. In a stuffed dinode,
32	* the dirents begin at offset sizeof(struct gfs2_dinode) from the beginning of
33	* the block. In leaves, they begin at offset sizeof(struct gfs2_leaf) from the
34	* beginning of the leaf block. The dirents reside in leaves when
35	*
36	* dip->i_diskflags & GFS2_DIF_EXHASH is true
37	*
38	* Otherwise, the dirents are "linear", within a single stuffed dinode block.
39	*
40	* When the dirents are in leaves, the actual contents of the directory file are
41	* used as an array of 64-bit block pointers pointing to the leaf blocks. The
42	* dirents are NOT in the directory file itself. There can be more than one
43	* block pointer in the array that points to the same leaf. In fact, when a
44	* directory is first converted from linear to exhash, all of the pointers
45	* point to the same leaf.
46	*
47	* When a leaf is completely full, the size of the hash table can be
48	* doubled unless it is already at the maximum size which is hard coded into
49	* GFS2_DIR_MAX_DEPTH. After that, leaves are chained together in a linked list,
50	* but never before the maximum hash table size has been reached.
51	*/
52
53	#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
54
55	#include <linux/slab.h>
56	#include <linux/spinlock.h>
57	#include <linux/buffer_head.h>
58	#include <linux/sort.h>
59	#include <linux/gfs2_ondisk.h>
60	#include <linux/crc32.h>
61	#include <linux/vmalloc.h>
62	#include <linux/bio.h>
63
64	#include "gfs2.h"
65	#include "incore.h"
66	#include "dir.h"
67	#include "glock.h"
68	#include "inode.h"
69	#include "meta_io.h"
70	#include "quota.h"
71	#include "rgrp.h"
72	#include "trans.h"
73	#include "bmap.h"
74	#include "util.h"
75
76	#define MAX_RA_BLOCKS 32 /* max read-ahead blocks */
77
78	#define gfs2_disk_hash2offset(h) (((u64)(h)) >> 1)
79	#define gfs2_dir_offset2hash(p) ((u32)(((u64)(p)) << 1))
80	#define GFS2_HASH_INDEX_MASK 0xffffc000
81	#define GFS2_USE_HASH_FLAG 0x2000
82
83	struct qstr gfs2_qdot __read_mostly;
84	struct qstr gfs2_qdotdot __read_mostly;
85
86	typedef int (*gfs2_dscan_t)(const struct gfs2_dirent *dent,
87	const struct qstr *name, void *opaque);
88
89	int gfs2_dir_get_new_buffer(struct gfs2_inode *ip, u64 block,
90	struct buffer_head **bhp)
91	{
92	struct buffer_head *bh;
93
94	bh = gfs2_meta_new(gl: ip->i_gl, blkno: block);
95	gfs2_trans_add_meta(gl: ip->i_gl, bh);
96	gfs2_metatype_set(bh, GFS2_METATYPE_JD, GFS2_FORMAT_JD);
97	gfs2_buffer_clear_tail(bh, head: sizeof(struct gfs2_meta_header));
98	*bhp = bh;
99	return 0;
100	}
101
102	static int gfs2_dir_get_existing_buffer(struct gfs2_inode *ip, u64 block,
103	struct buffer_head **bhp)
104	{
105	struct buffer_head *bh;
106	int error;
107
108	error = gfs2_meta_read(gl: ip->i_gl, blkno: block, DIO_WAIT, rahead: 0, bhp: &bh);
109	if (error)
110	return error;
111	if (gfs2_metatype_check(GFS2_SB(&ip->i_inode), bh, GFS2_METATYPE_JD)) {
112	brelse(bh);
113	return -EIO;
114	}
115	*bhp = bh;
116	return 0;
117	}
118
119	static int gfs2_dir_write_stuffed(struct gfs2_inode *ip, const char *buf,
120	unsigned int offset, unsigned int size)
121	{
122	struct buffer_head *dibh;
123	int error;
124
125	error = gfs2_meta_inode_buffer(ip, bhp: &dibh);
126	if (error)
127	return error;
128
129	gfs2_trans_add_meta(gl: ip->i_gl, bh: dibh);
130	memcpy(dibh->b_data + offset + sizeof(struct gfs2_dinode), buf, size);
131	if (ip->i_inode.i_size < offset + size)
132	i_size_write(inode: &ip->i_inode, i_size: offset + size);
133	inode_set_mtime_to_ts(inode: &ip->i_inode, ts: inode_set_ctime_current(inode: &ip->i_inode));
134	gfs2_dinode_out(ip, buf: dibh->b_data);
135
136	brelse(bh: dibh);
137
138	return size;
139	}
140
141
142
143	/**
144	* gfs2_dir_write_data - Write directory information to the inode
145	* @ip: The GFS2 inode
146	* @buf: The buffer containing information to be written
147	* @offset: The file offset to start writing at
148	* @size: The amount of data to write
149	*
150	* Returns: The number of bytes correctly written or error code
151	*/
152	static int gfs2_dir_write_data(struct gfs2_inode *ip, const char *buf,
153	u64 offset, unsigned int size)
154	{
155	struct gfs2_sbd *sdp = GFS2_SB(inode: &ip->i_inode);
156	struct buffer_head *dibh;
157	u64 lblock, dblock;
158	u32 extlen = 0;
159	unsigned int o;
160	int copied = 0;
161	int error = 0;
162	bool new = false;
163
164	if (!size)
165	return 0;
166
167	if (gfs2_is_stuffed(ip) && offset + size <= gfs2_max_stuffed_size(ip))
168	return gfs2_dir_write_stuffed(ip, buf, offset: (unsigned int)offset,
169	size);
170
171	if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
172	return -EINVAL;
173
174	if (gfs2_is_stuffed(ip)) {
175	error = gfs2_unstuff_dinode(ip);
176	if (error)
177	return error;
178	}
179
180	lblock = offset;
181	o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);
182
183	while (copied < size) {
184	unsigned int amount;
185	struct buffer_head *bh;
186
187	amount = size - copied;
188	if (amount > sdp->sd_sb.sb_bsize - o)
189	amount = sdp->sd_sb.sb_bsize - o;
190
191	if (!extlen) {
192	extlen = 1;
193	error = gfs2_alloc_extent(inode: &ip->i_inode, lblock, dblock: &dblock,
194	extlen: &extlen, new: &new);
195	if (error)
196	goto fail;
197	error = -EIO;
198	if (gfs2_assert_withdraw(sdp, dblock))
199	goto fail;
200	}
201
202	if (amount == sdp->sd_jbsize || new)
203	error = gfs2_dir_get_new_buffer(ip, block: dblock, bhp: &bh);
204	else
205	error = gfs2_dir_get_existing_buffer(ip, block: dblock, bhp: &bh);
206
207	if (error)
208	goto fail;
209
210	gfs2_trans_add_meta(gl: ip->i_gl, bh);
211	memcpy(bh->b_data + o, buf, amount);
212	brelse(bh);
213
214	buf += amount;
215	copied += amount;
216	lblock++;
217	dblock++;
218	extlen--;
219
220	o = sizeof(struct gfs2_meta_header);
221	}
222
223	out:
224	error = gfs2_meta_inode_buffer(ip, bhp: &dibh);
225	if (error)
226	return error;
227
228	if (ip->i_inode.i_size < offset + copied)
229	i_size_write(inode: &ip->i_inode, i_size: offset + copied);
230	inode_set_mtime_to_ts(inode: &ip->i_inode, ts: inode_set_ctime_current(inode: &ip->i_inode));
231
232	gfs2_trans_add_meta(gl: ip->i_gl, bh: dibh);
233	gfs2_dinode_out(ip, buf: dibh->b_data);
234	brelse(bh: dibh);
235
236	return copied;
237	fail:
238	if (copied)
239	goto out;
240	return error;
241	}
242
243	static int gfs2_dir_read_stuffed(struct gfs2_inode *ip, __be64 *buf,
244	unsigned int size)
245	{
246	struct buffer_head *dibh;
247	int error;
248
249	error = gfs2_meta_inode_buffer(ip, bhp: &dibh);
250	if (!error) {
251	memcpy(buf, dibh->b_data + sizeof(struct gfs2_dinode), size);
252	brelse(bh: dibh);
253	}
254
255	return (error) ? error : size;
256	}
257
258
259	/**
260	* gfs2_dir_read_data - Read a data from a directory inode
261	* @ip: The GFS2 Inode
262	* @buf: The buffer to place result into
263	* @size: Amount of data to transfer
264	*
265	* Returns: The amount of data actually copied or the error
266	*/
267	static int gfs2_dir_read_data(struct gfs2_inode *ip, __be64 *buf,
268	unsigned int size)
269	{
270	struct gfs2_sbd *sdp = GFS2_SB(inode: &ip->i_inode);
271	u64 lblock, dblock;
272	u32 extlen = 0;
273	unsigned int o;
274	int copied = 0;
275	int error = 0;
276
277	if (gfs2_is_stuffed(ip))
278	return gfs2_dir_read_stuffed(ip, buf, size);
279
280	if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
281	return -EINVAL;
282
283	lblock = 0;
284	o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);
285
286	while (copied < size) {
287	unsigned int amount;
288	struct buffer_head *bh;
289
290	amount = size - copied;
291	if (amount > sdp->sd_sb.sb_bsize - o)
292	amount = sdp->sd_sb.sb_bsize - o;
293
294	if (!extlen) {
295	extlen = 32;
296	error = gfs2_get_extent(inode: &ip->i_inode, lblock,
297	dblock: &dblock, extlen: &extlen);
298	if (error || !dblock)
299	goto fail;
300	BUG_ON(extlen < 1);
301	bh = gfs2_meta_ra(gl: ip->i_gl, dblock, extlen);
302	} else {
303	error = gfs2_meta_read(gl: ip->i_gl, blkno: dblock, DIO_WAIT, rahead: 0, bhp: &bh);
304	if (error)
305	goto fail;
306	}
307	error = gfs2_metatype_check(sdp, bh, GFS2_METATYPE_JD);
308	if (error) {
309	brelse(bh);
310	goto fail;
311	}
312	dblock++;
313	extlen--;
314	memcpy(buf, bh->b_data + o, amount);
315	brelse(bh);
316	buf += (amount/sizeof(__be64));
317	copied += amount;
318	lblock++;
319	o = sizeof(struct gfs2_meta_header);
320	}
321
322	return copied;
323	fail:
324	return (copied) ? copied : error;
325	}
326
327	/**
328	* gfs2_dir_get_hash_table - Get pointer to the dir hash table
329	* @ip: The inode in question
330	*
331	* Returns: The hash table or an error
332	*/
333
334	static __be64 *gfs2_dir_get_hash_table(struct gfs2_inode *ip)
335	{
336	struct inode *inode = &ip->i_inode;
337	int ret;
338	u32 hsize;
339	__be64 *hc;
340
341	BUG_ON(!(ip->i_diskflags & GFS2_DIF_EXHASH));
342
343	hc = ip->i_hash_cache;
344	if (hc)
345	return hc;
346
347	hsize = BIT(ip->i_depth);
348	hsize *= sizeof(__be64);
349	if (hsize != i_size_read(inode: &ip->i_inode)) {
350	gfs2_consist_inode(ip);
351	return ERR_PTR(error: -EIO);
352	}
353
354	hc = kmalloc(size: hsize, GFP_NOFS | __GFP_NOWARN);
355	if (hc == NULL)
356	hc = __vmalloc(size: hsize, GFP_NOFS);
357
358	if (hc == NULL)
359	return ERR_PTR(error: -ENOMEM);
360
361	ret = gfs2_dir_read_data(ip, buf: hc, size: hsize);
362	if (ret < 0) {
363	kvfree(addr: hc);
364	return ERR_PTR(error: ret);
365	}
366
367	spin_lock(lock: &inode->i_lock);
368	if (likely(!ip->i_hash_cache)) {
369	ip->i_hash_cache = hc;
370	hc = NULL;
371	}
372	spin_unlock(lock: &inode->i_lock);
373	kvfree(addr: hc);
374
375	return ip->i_hash_cache;
376	}
377
378	/**
379	* gfs2_dir_hash_inval - Invalidate dir hash
380	* @ip: The directory inode
381	*
382	* Must be called with an exclusive glock, or during glock invalidation.
383	*/
384	void gfs2_dir_hash_inval(struct gfs2_inode *ip)
385	{
386	__be64 *hc;
387
388	spin_lock(lock: &ip->i_inode.i_lock);
389	hc = ip->i_hash_cache;
390	ip->i_hash_cache = NULL;
391	spin_unlock(lock: &ip->i_inode.i_lock);
392
393	kvfree(addr: hc);
394	}
395
396	static inline int gfs2_dirent_sentinel(const struct gfs2_dirent *dent)
397	{
398	return dent->de_inum.no_addr == 0 || dent->de_inum.no_formal_ino == 0;
399	}
400
401	static inline int __gfs2_dirent_find(const struct gfs2_dirent *dent,
402	const struct qstr *name, int ret)
403	{
404	if (!gfs2_dirent_sentinel(dent) &&
405	be32_to_cpu(dent->de_hash) == name->hash &&
406	be16_to_cpu(dent->de_name_len) == name->len &&
407	memcmp(p: dent+1, q: name->name, size: name->len) == 0)
408	return ret;
409	return 0;
410	}
411
412	static int gfs2_dirent_find(const struct gfs2_dirent *dent,
413	const struct qstr *name,
414	void *opaque)
415	{
416	return __gfs2_dirent_find(dent, name, ret: 1);
417	}
418
419	static int gfs2_dirent_prev(const struct gfs2_dirent *dent,
420	const struct qstr *name,
421	void *opaque)
422	{
423	return __gfs2_dirent_find(dent, name, ret: 2);
424	}
425
426	/*
427	* name->name holds ptr to start of block.
428	* name->len holds size of block.
429	*/
430	static int gfs2_dirent_last(const struct gfs2_dirent *dent,
431	const struct qstr *name,
432	void *opaque)
433	{
434	const char *start = name->name;
435	const char *end = (const char *)dent + be16_to_cpu(dent->de_rec_len);
436	if (name->len == (end - start))
437	return 1;
438	return 0;
439	}
440
441	/* Look for the dirent that contains the offset specified in data. Once we
442	* find that dirent, there must be space available there for the new dirent */
443	static int gfs2_dirent_find_offset(const struct gfs2_dirent *dent,
444	const struct qstr *name,
445	void *ptr)
446	{
447	unsigned required = GFS2_DIRENT_SIZE(name->len);
448	unsigned actual = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));
449	unsigned totlen = be16_to_cpu(dent->de_rec_len);
450
451	if (ptr < (void *)dent || ptr >= (void *)dent + totlen)
452	return 0;
453	if (gfs2_dirent_sentinel(dent))
454	actual = 0;
455	if (ptr < (void *)dent + actual)
456	return -1;
457	if ((void *)dent + totlen >= ptr + required)
458	return 1;
459	return -1;
460	}
461
462	static int gfs2_dirent_find_space(const struct gfs2_dirent *dent,
463	const struct qstr *name,
464	void *opaque)
465	{
466	unsigned required = GFS2_DIRENT_SIZE(name->len);
467	unsigned actual = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));
468	unsigned totlen = be16_to_cpu(dent->de_rec_len);
469
470	if (gfs2_dirent_sentinel(dent))
471	actual = 0;
472	if (totlen - actual >= required)
473	return 1;
474	return 0;
475	}
476
477	struct dirent_gather {
478	const struct gfs2_dirent **pdent;
479	unsigned offset;
480	};
481
482	static int gfs2_dirent_gather(const struct gfs2_dirent *dent,
483	const struct qstr *name,
484	void *opaque)
485	{
486	struct dirent_gather *g = opaque;
487	if (!gfs2_dirent_sentinel(dent)) {
488	g->pdent[g->offset++] = dent;
489	}
490	return 0;
491	}
492
493	/*
494	* Other possible things to check:
495	* - Inode located within filesystem size (and on valid block)
496	* - Valid directory entry type
497	* Not sure how heavy-weight we want to make this... could also check
498	* hash is correct for example, but that would take a lot of extra time.
499	* For now the most important thing is to check that the various sizes
500	* are correct.
501	*/
502	static int gfs2_check_dirent(struct gfs2_sbd *sdp,
503	struct gfs2_dirent *dent, unsigned int offset,
504	unsigned int size, unsigned int len, int first)
505	{
506	const char *msg = "gfs2_dirent too small";
507	if (unlikely(size < sizeof(struct gfs2_dirent)))
508	goto error;
509	msg = "gfs2_dirent misaligned";
510	if (unlikely(offset & 0x7))
511	goto error;
512	msg = "gfs2_dirent points beyond end of block";
513	if (unlikely(offset + size > len))
514	goto error;
515	msg = "zero inode number";
516	if (unlikely(!first && gfs2_dirent_sentinel(dent)))
517	goto error;
518	msg = "name length is greater than space in dirent";
519	if (!gfs2_dirent_sentinel(dent) &&
520	unlikely(sizeof(struct gfs2_dirent)+be16_to_cpu(dent->de_name_len) >
521	size))
522	goto error;
523	return 0;
524	error:
525	fs_warn(sdp, "%s: %s (%s)\n",
526	__func__, msg, first ? "first in block" : "not first in block");
527	return -EIO;
528	}
529
530	static int gfs2_dirent_offset(struct gfs2_sbd *sdp, const void *buf)
531	{
532	const struct gfs2_meta_header *h = buf;
533	int offset;
534
535	BUG_ON(buf == NULL);
536
537	switch(be32_to_cpu(h->mh_type)) {
538	case GFS2_METATYPE_LF:
539	offset = sizeof(struct gfs2_leaf);
540	break;
541	case GFS2_METATYPE_DI:
542	offset = sizeof(struct gfs2_dinode);
543	break;
544	default:
545	goto wrong_type;
546	}
547	return offset;
548	wrong_type:
549	fs_warn(sdp, "%s: wrong block type %u\n", __func__,
550	be32_to_cpu(h->mh_type));
551	return -1;
552	}
553
554	static struct gfs2_dirent *gfs2_dirent_scan(struct inode *inode, void *buf,
555	unsigned int len, gfs2_dscan_t scan,
556	const struct qstr *name,
557	void *opaque)
558	{
559	struct gfs2_dirent *dent, *prev;
560	unsigned offset;
561	unsigned size;
562	int ret = 0;
563
564	ret = gfs2_dirent_offset(sdp: GFS2_SB(inode), buf);
565	if (ret < 0)
566	goto consist_inode;
567
568	offset = ret;
569	prev = NULL;
570	dent = buf + offset;
571	size = be16_to_cpu(dent->de_rec_len);
572	if (gfs2_check_dirent(sdp: GFS2_SB(inode), dent, offset, size, len, first: 1))
573	goto consist_inode;
574	do {
575	ret = scan(dent, name, opaque);
576	if (ret)
577	break;
578	offset += size;
579	if (offset == len)
580	break;
581	prev = dent;
582	dent = buf + offset;
583	size = be16_to_cpu(dent->de_rec_len);
584	if (gfs2_check_dirent(sdp: GFS2_SB(inode), dent, offset, size,
585	len, first: 0))
586	goto consist_inode;
587	} while(1);
588
589	switch(ret) {
590	case 0:
591	return NULL;
592	case 1:
593	return dent;
594	case 2:
595	return prev ? prev : dent;
596	default:
597	BUG_ON(ret > 0);
598	return ERR_PTR(error: ret);
599	}
600
601	consist_inode:
602	gfs2_consist_inode(GFS2_I(inode));
603	return ERR_PTR(error: -EIO);
604	}
605
606	static int dirent_check_reclen(struct gfs2_inode *dip,
607	const struct gfs2_dirent *d, const void *end_p)
608	{
609	const void *ptr = d;
610	u16 rec_len = be16_to_cpu(d->de_rec_len);
611
612	if (unlikely(rec_len < sizeof(struct gfs2_dirent)))
613	goto broken;
614	ptr += rec_len;
615	if (ptr < end_p)
616	return rec_len;
617	if (ptr == end_p)
618	return -ENOENT;
619	broken:
620	gfs2_consist_inode(dip);
621	return -EIO;
622	}
623
624	/**
625	* dirent_next - Next dirent
626	* @dip: the directory
627	* @bh: The buffer
628	* @dent: Pointer to list of dirents
629	*
630	* Returns: 0 on success, error code otherwise
631	*/
632
633	static int dirent_next(struct gfs2_inode *dip, struct buffer_head *bh,
634	struct gfs2_dirent **dent)
635	{
636	struct gfs2_dirent *cur = *dent, *tmp;
637	char *bh_end = bh->b_data + bh->b_size;
638	int ret;
639
640	ret = dirent_check_reclen(dip, d: cur, end_p: bh_end);
641	if (ret < 0)
642	return ret;
643
644	tmp = (void *)cur + ret;
645	ret = dirent_check_reclen(dip, d: tmp, end_p: bh_end);
646	if (ret == -EIO)
647	return ret;
648
649	/* Only the first dent could ever have de_inum.no_addr == 0 */
650	if (gfs2_dirent_sentinel(dent: tmp)) {
651	gfs2_consist_inode(dip);
652	return -EIO;
653	}
654
655	*dent = tmp;
656	return 0;
657	}
658
659	/**
660	* dirent_del - Delete a dirent
661	* @dip: The GFS2 inode
662	* @bh: The buffer
663	* @prev: The previous dirent
664	* @cur: The current dirent
665	*
666	*/
667
668	static void dirent_del(struct gfs2_inode *dip, struct buffer_head *bh,
669	struct gfs2_dirent *prev, struct gfs2_dirent *cur)
670	{
671	u16 cur_rec_len, prev_rec_len;
672
673	if (gfs2_dirent_sentinel(dent: cur)) {
674	gfs2_consist_inode(dip);
675	return;
676	}
677
678	gfs2_trans_add_meta(gl: dip->i_gl, bh);
679
680	/* If there is no prev entry, this is the first entry in the block.
681	The de_rec_len is already as big as it needs to be. Just zero
682	out the inode number and return. */
683
684	if (!prev) {
685	cur->de_inum.no_addr = 0;
686	cur->de_inum.no_formal_ino = 0;
687	return;
688	}
689
690	/* Combine this dentry with the previous one. */
691
692	prev_rec_len = be16_to_cpu(prev->de_rec_len);
693	cur_rec_len = be16_to_cpu(cur->de_rec_len);
694
695	if ((char *)prev + prev_rec_len != (char *)cur)
696	gfs2_consist_inode(dip);
697	if ((char *)cur + cur_rec_len > bh->b_data + bh->b_size)
698	gfs2_consist_inode(dip);
699
700	prev_rec_len += cur_rec_len;
701	prev->de_rec_len = cpu_to_be16(prev_rec_len);
702	}
703
704
705	static struct gfs2_dirent *do_init_dirent(struct inode *inode,
706	struct gfs2_dirent *dent,
707	const struct qstr *name,
708	struct buffer_head *bh,
709	unsigned offset)
710	{
711	struct gfs2_inode *ip = GFS2_I(inode);
712	struct gfs2_dirent *ndent;
713	unsigned totlen;
714
715	totlen = be16_to_cpu(dent->de_rec_len);
716	BUG_ON(offset + name->len > totlen);
717	gfs2_trans_add_meta(gl: ip->i_gl, bh);
718	ndent = (struct gfs2_dirent *)((char *)dent + offset);
719	dent->de_rec_len = cpu_to_be16(offset);
720	gfs2_qstr2dirent(name, reclen: totlen - offset, dent: ndent);
721	return ndent;
722	}
723
724
725	/*
726	* Takes a dent from which to grab space as an argument. Returns the
727	* newly created dent.
728	*/
729	static struct gfs2_dirent *gfs2_init_dirent(struct inode *inode,
730	struct gfs2_dirent *dent,
731	const struct qstr *name,
732	struct buffer_head *bh)
733	{
734	unsigned offset = 0;
735
736	if (!gfs2_dirent_sentinel(dent))
737	offset = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));
738	return do_init_dirent(inode, dent, name, bh, offset);
739	}
740
741	static struct gfs2_dirent *gfs2_dirent_split_alloc(struct inode *inode,
742	struct buffer_head *bh,
743	const struct qstr *name,
744	void *ptr)
745	{
746	struct gfs2_dirent *dent;
747	dent = gfs2_dirent_scan(inode, buf: bh->b_data, len: bh->b_size,
748	scan: gfs2_dirent_find_offset, name, opaque: ptr);
749	if (IS_ERR_OR_NULL(ptr: dent))
750	return dent;
751	return do_init_dirent(inode, dent, name, bh,
752	offset: (unsigned)(ptr - (void *)dent));
753	}
754
755	static int get_leaf(struct gfs2_inode *dip, u64 leaf_no,
756	struct buffer_head **bhp)
757	{
758	int error;
759
760	error = gfs2_meta_read(gl: dip->i_gl, blkno: leaf_no, DIO_WAIT, rahead: 0, bhp);
761	if (!error && gfs2_metatype_check(GFS2_SB(&dip->i_inode), *bhp, GFS2_METATYPE_LF)) {
762	/* pr_info("block num=%llu\n", leaf_no); */
763	error = -EIO;
764	}
765
766	return error;
767	}
768
769	/**
770	* get_leaf_nr - Get a leaf number associated with the index
771	* @dip: The GFS2 inode
772	* @index: hash table index of the targeted leaf
773	* @leaf_out: Resulting leaf block number
774	*
775	* Returns: 0 on success, error code otherwise
776	*/
777
778	static int get_leaf_nr(struct gfs2_inode *dip, u32 index, u64 *leaf_out)
779	{
780	__be64 *hash;
781	int error;
782
783	hash = gfs2_dir_get_hash_table(ip: dip);
784	error = PTR_ERR_OR_ZERO(ptr: hash);
785
786	if (!error)
787	*leaf_out = be64_to_cpu(*(hash + index));
788
789	return error;
790	}
791
792	static int get_first_leaf(struct gfs2_inode *dip, u32 index,
793	struct buffer_head **bh_out)
794	{
795	u64 leaf_no;
796	int error;
797
798	error = get_leaf_nr(dip, index, leaf_out: &leaf_no);
799	if (!error)
800	error = get_leaf(dip, leaf_no, bhp: bh_out);
801
802	return error;
803	}
804
805	static struct gfs2_dirent *gfs2_dirent_search(struct inode *inode,
806	const struct qstr *name,
807	gfs2_dscan_t scan,
808	struct buffer_head **pbh)
809	{
810	struct buffer_head *bh;
811	struct gfs2_dirent *dent;
812	struct gfs2_inode *ip = GFS2_I(inode);
813	int error;
814
815	if (ip->i_diskflags & GFS2_DIF_EXHASH) {
816	struct gfs2_leaf *leaf;
817	unsigned int hsize = BIT(ip->i_depth);
818	unsigned int index;
819	u64 ln;
820	if (hsize * sizeof(u64) != i_size_read(inode)) {
821	gfs2_consist_inode(ip);
822	return ERR_PTR(error: -EIO);
823	}
824
825	index = name->hash >> (32 - ip->i_depth);
826	error = get_first_leaf(dip: ip, index, bh_out: &bh);
827	if (error)
828	return ERR_PTR(error);
829	do {
830	dent = gfs2_dirent_scan(inode, buf: bh->b_data, len: bh->b_size,
831	scan, name, NULL);
832	if (dent)
833	goto got_dent;
834	leaf = (struct gfs2_leaf *)bh->b_data;
835	ln = be64_to_cpu(leaf->lf_next);
836	brelse(bh);
837	if (!ln)
838	break;
839
840	error = get_leaf(dip: ip, leaf_no: ln, bhp: &bh);
841	} while(!error);
842
843	return error ? ERR_PTR(error) : NULL;
844	}
845
846
847	error = gfs2_meta_inode_buffer(ip, bhp: &bh);
848	if (error)
849	return ERR_PTR(error);
850	dent = gfs2_dirent_scan(inode, buf: bh->b_data, len: bh->b_size, scan, name, NULL);
851	got_dent:
852	if (IS_ERR_OR_NULL(ptr: dent)) {
853	brelse(bh);
854	bh = NULL;
855	}
856	*pbh = bh;
857	return dent;
858	}
859
860	static struct gfs2_leaf *new_leaf(struct inode *inode, struct buffer_head **pbh, u16 depth)
861	{
862	struct gfs2_inode *ip = GFS2_I(inode);
863	unsigned int n = 1;
864	u64 bn;
865	int error;
866	struct buffer_head *bh;
867	struct gfs2_leaf *leaf;
868	struct gfs2_dirent *dent;
869	struct timespec64 tv = current_time(inode);
870
871	error = gfs2_alloc_blocks(ip, bn: &bn, n: &n, dinode: 0);
872	if (error)
873	return NULL;
874	bh = gfs2_meta_new(gl: ip->i_gl, blkno: bn);
875	if (!bh)
876	return NULL;
877
878	gfs2_trans_remove_revoke(sdp: GFS2_SB(inode), blkno: bn, len: 1);
879	gfs2_trans_add_meta(gl: ip->i_gl, bh);
880	gfs2_metatype_set(bh, GFS2_METATYPE_LF, GFS2_FORMAT_LF);
881	leaf = (struct gfs2_leaf *)bh->b_data;
882	leaf->lf_depth = cpu_to_be16(depth);
883	leaf->lf_entries = 0;
884	leaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
885	leaf->lf_next = 0;
886	leaf->lf_inode = cpu_to_be64(ip->i_no_addr);
887	leaf->lf_dist = cpu_to_be32(1);
888	leaf->lf_nsec = cpu_to_be32(tv.tv_nsec);
889	leaf->lf_sec = cpu_to_be64(tv.tv_sec);
890	memset(leaf->lf_reserved2, 0, sizeof(leaf->lf_reserved2));
891	dent = (struct gfs2_dirent *)(leaf+1);
892	gfs2_qstr2dirent(name: &empty_name, reclen: bh->b_size - sizeof(struct gfs2_leaf), dent);
893	*pbh = bh;
894	return leaf;
895	}
896
897	/**
898	* dir_make_exhash - Convert a stuffed directory into an ExHash directory
899	* @inode: The directory inode to be converted to exhash
900	*
901	* Returns: 0 on success, error code otherwise
902	*/
903
904	static int dir_make_exhash(struct inode *inode)
905	{
906	struct gfs2_inode *dip = GFS2_I(inode);
907	struct gfs2_sbd *sdp = GFS2_SB(inode);
908	struct gfs2_dirent *dent;
909	struct qstr args;
910	struct buffer_head *bh, *dibh;
911	struct gfs2_leaf *leaf;
912	int y;
913	u32 x;
914	__be64 *lp;
915	u64 bn;
916	int error;
917
918	error = gfs2_meta_inode_buffer(ip: dip, bhp: &dibh);
919	if (error)
920	return error;
921
922	/* Turn over a new leaf */
923
924	leaf = new_leaf(inode, pbh: &bh, depth: 0);
925	if (!leaf)
926	return -ENOSPC;
927	bn = bh->b_blocknr;
928
929	gfs2_assert(sdp, dip->i_entries < BIT(16));
930	leaf->lf_entries = cpu_to_be16(dip->i_entries);
931
932	/* Copy dirents */
933
934	gfs2_buffer_copy_tail(to_bh: bh, to_head: sizeof(struct gfs2_leaf), from_bh: dibh,
935	from_head: sizeof(struct gfs2_dinode));
936
937	/* Find last entry */
938
939	x = 0;
940	args.len = bh->b_size - sizeof(struct gfs2_dinode) +
941	sizeof(struct gfs2_leaf);
942	args.name = bh->b_data;
943	dent = gfs2_dirent_scan(inode: &dip->i_inode, buf: bh->b_data, len: bh->b_size,
944	scan: gfs2_dirent_last, name: &args, NULL);
945	if (!dent) {
946	brelse(bh);
947	brelse(bh: dibh);
948	return -EIO;
949	}
950	if (IS_ERR(ptr: dent)) {
951	brelse(bh);
952	brelse(bh: dibh);
953	return PTR_ERR(ptr: dent);
954	}
955
956	/* Adjust the last dirent's record length
957	(Remember that dent still points to the last entry.) */
958
959	dent->de_rec_len = cpu_to_be16(be16_to_cpu(dent->de_rec_len) +
960	sizeof(struct gfs2_dinode) -
961	sizeof(struct gfs2_leaf));
962
963	brelse(bh);
964
965	/* We're done with the new leaf block, now setup the new
966	hash table. */
967
968	gfs2_trans_add_meta(gl: dip->i_gl, bh: dibh);
969	gfs2_buffer_clear_tail(bh: dibh, head: sizeof(struct gfs2_dinode));
970
971	lp = (__be64 *)(dibh->b_data + sizeof(struct gfs2_dinode));
972
973	for (x = sdp->sd_hash_ptrs; x--; lp++)
974	*lp = cpu_to_be64(bn);
975
976	i_size_write(inode, i_size: sdp->sd_sb.sb_bsize / 2);
977	gfs2_add_inode_blocks(inode: &dip->i_inode, change: 1);
978	dip->i_diskflags |= GFS2_DIF_EXHASH;
979
980	for (x = sdp->sd_hash_ptrs, y = -1; x; x >>= 1, y++) ;
981	dip->i_depth = y;
982
983	gfs2_dinode_out(ip: dip, buf: dibh->b_data);
984
985	brelse(bh: dibh);
986
987	return 0;
988	}
989
990	/**
991	* dir_split_leaf - Split a leaf block into two
992	* @inode: The directory inode to be split
993	* @name: name of the dirent we're trying to insert
994	*
995	* Returns: 0 on success, error code on failure
996	*/
997
998	static int dir_split_leaf(struct inode *inode, const struct qstr *name)
999	{
1000	struct gfs2_inode *dip = GFS2_I(inode);
1001	struct buffer_head *nbh, *obh, *dibh;
1002	struct gfs2_leaf *nleaf, *oleaf;
1003	struct gfs2_dirent *dent = NULL, *prev = NULL, *next = NULL, *new;
1004	u32 start, len, half_len, divider;
1005	u64 bn, leaf_no;
1006	__be64 *lp;
1007	u32 index;
1008	int x;
1009	int error;
1010
1011	index = name->hash >> (32 - dip->i_depth);
1012	error = get_leaf_nr(dip, index, leaf_out: &leaf_no);
1013	if (error)
1014	return error;
1015
1016	/* Get the old leaf block */
1017	error = get_leaf(dip, leaf_no, bhp: &obh);
1018	if (error)
1019	return error;
1020
1021	oleaf = (struct gfs2_leaf *)obh->b_data;
1022	if (dip->i_depth == be16_to_cpu(oleaf->lf_depth)) {
1023	brelse(bh: obh);
1024	return 1; /* can't split */
1025	}
1026
1027	gfs2_trans_add_meta(gl: dip->i_gl, bh: obh);
1028
1029	nleaf = new_leaf(inode, pbh: &nbh, be16_to_cpu(oleaf->lf_depth) + 1);
1030	if (!nleaf) {
1031	brelse(bh: obh);
1032	return -ENOSPC;
1033	}
1034	bn = nbh->b_blocknr;
1035
1036	/* Compute the start and len of leaf pointers in the hash table. */
1037	len = BIT(dip->i_depth - be16_to_cpu(oleaf->lf_depth));
1038	half_len = len >> 1;
1039	if (!half_len) {
1040	fs_warn(GFS2_SB(inode), "i_depth %u lf_depth %u index %u\n",
1041	dip->i_depth, be16_to_cpu(oleaf->lf_depth), index);
1042	gfs2_consist_inode(dip);
1043	error = -EIO;
1044	goto fail_brelse;
1045	}
1046
1047	start = (index & ~(len - 1));
1048
1049	/* Change the pointers.
1050	Don't bother distinguishing stuffed from non-stuffed.
1051	This code is complicated enough already. */
1052	lp = kmalloc_array(n: half_len, size: sizeof(__be64), GFP_NOFS);
1053	if (!lp) {
1054	error = -ENOMEM;
1055	goto fail_brelse;
1056	}
1057
1058	/* Change the pointers */
1059	for (x = 0; x < half_len; x++)
1060	lp[x] = cpu_to_be64(bn);
1061
1062	gfs2_dir_hash_inval(ip: dip);
1063
1064	error = gfs2_dir_write_data(ip: dip, buf: (char *)lp, offset: start * sizeof(u64),
1065	size: half_len * sizeof(u64));
1066	if (error != half_len * sizeof(u64)) {
1067	if (error >= 0)
1068	error = -EIO;
1069	goto fail_lpfree;
1070	}
1071
1072	kfree(objp: lp);
1073
1074	/* Compute the divider */
1075	divider = (start + half_len) << (32 - dip->i_depth);
1076
1077	/* Copy the entries */
1078	dent = (struct gfs2_dirent *)(obh->b_data + sizeof(struct gfs2_leaf));
1079
1080	do {
1081	next = dent;
1082	if (dirent_next(dip, bh: obh, dent: &next))
1083	next = NULL;
1084
1085	if (!gfs2_dirent_sentinel(dent) &&
1086	be32_to_cpu(dent->de_hash) < divider) {
1087	struct qstr str;
1088	void *ptr = ((char *)dent - obh->b_data) + nbh->b_data;
1089	str.name = (char*)(dent+1);
1090	str.len = be16_to_cpu(dent->de_name_len);
1091	str.hash = be32_to_cpu(dent->de_hash);
1092	new = gfs2_dirent_split_alloc(inode, bh: nbh, name: &str, ptr);
1093	if (IS_ERR(ptr: new)) {
1094	error = PTR_ERR(ptr: new);
1095	break;
1096	}
1097
1098	new->de_inum = dent->de_inum; /* No endian worries */
1099	new->de_type = dent->de_type; /* No endian worries */
1100	be16_add_cpu(var: &nleaf->lf_entries, val: 1);
1101
1102	dirent_del(dip, bh: obh, prev, cur: dent);
1103
1104	if (!oleaf->lf_entries)
1105	gfs2_consist_inode(dip);
1106	be16_add_cpu(var: &oleaf->lf_entries, val: -1);
1107
1108	if (!prev)
1109	prev = dent;
1110	} else {
1111	prev = dent;
1112	}
1113	dent = next;
1114	} while (dent);
1115
1116	oleaf->lf_depth = nleaf->lf_depth;
1117
1118	error = gfs2_meta_inode_buffer(ip: dip, bhp: &dibh);
1119	if (!gfs2_assert_withdraw(GFS2_SB(&dip->i_inode), !error)) {
1120	gfs2_trans_add_meta(gl: dip->i_gl, bh: dibh);
1121	gfs2_add_inode_blocks(inode: &dip->i_inode, change: 1);
1122	gfs2_dinode_out(ip: dip, buf: dibh->b_data);
1123	brelse(bh: dibh);
1124	}
1125
1126	brelse(bh: obh);
1127	brelse(bh: nbh);
1128
1129	return error;
1130
1131	fail_lpfree:
1132	kfree(objp: lp);
1133
1134	fail_brelse:
1135	brelse(bh: obh);
1136	brelse(bh: nbh);
1137	return error;
1138	}
1139
1140	/**
1141	* dir_double_exhash - Double size of ExHash table
1142	* @dip: The GFS2 dinode
1143	*
1144	* Returns: 0 on success, error code on failure
1145	*/
1146
1147	static int dir_double_exhash(struct gfs2_inode *dip)
1148	{
1149	struct buffer_head *dibh;
1150	u32 hsize;
1151	u32 hsize_bytes;
1152	__be64 *hc;
1153	__be64 *hc2, *h;
1154	int x;
1155	int error = 0;
1156
1157	hsize = BIT(dip->i_depth);
1158	hsize_bytes = hsize * sizeof(__be64);
1159
1160	hc = gfs2_dir_get_hash_table(ip: dip);
1161	if (IS_ERR(ptr: hc))
1162	return PTR_ERR(ptr: hc);
1163
1164	hc2 = kmalloc_array(n: hsize_bytes, size: 2, GFP_NOFS | __GFP_NOWARN);
1165	if (hc2 == NULL)
1166	hc2 = __vmalloc(size: hsize_bytes * 2, GFP_NOFS);
1167
1168	if (!hc2)
1169	return -ENOMEM;
1170
1171	h = hc2;
1172	error = gfs2_meta_inode_buffer(ip: dip, bhp: &dibh);
1173	if (error)
1174	goto out_kfree;
1175
1176	for (x = 0; x < hsize; x++) {
1177	*h++ = *hc;
1178	*h++ = *hc;
1179	hc++;
1180	}
1181
1182	error = gfs2_dir_write_data(ip: dip, buf: (char *)hc2, offset: 0, size: hsize_bytes * 2);
1183	if (error != (hsize_bytes * 2))
1184	goto fail;
1185
1186	gfs2_dir_hash_inval(ip: dip);
1187	dip->i_hash_cache = hc2;
1188	dip->i_depth++;
1189	gfs2_dinode_out(ip: dip, buf: dibh->b_data);
1190	brelse(bh: dibh);
1191	return 0;
1192
1193	fail:
1194	/* Replace original hash table & size */
1195	gfs2_dir_write_data(ip: dip, buf: (char *)hc, offset: 0, size: hsize_bytes);
1196	i_size_write(inode: &dip->i_inode, i_size: hsize_bytes);
1197	gfs2_dinode_out(ip: dip, buf: dibh->b_data);
1198	brelse(bh: dibh);
1199	out_kfree:
1200	kvfree(addr: hc2);
1201	return error;
1202	}
1203
1204	/**
1205	* compare_dents - compare directory entries by hash value
1206	* @a: first dent
1207	* @b: second dent
1208	*
1209	* When comparing the hash entries of @a to @b:
1210	* gt: returns 1
1211	* lt: returns -1
1212	* eq: returns 0
1213	*/
1214
1215	static int compare_dents(const void *a, const void *b)
1216	{
1217	const struct gfs2_dirent *dent_a, *dent_b;
1218	u32 hash_a, hash_b;
1219	int ret = 0;
1220
1221	dent_a = *(const struct gfs2_dirent **)a;
1222	hash_a = dent_a->de_cookie;
1223
1224	dent_b = *(const struct gfs2_dirent **)b;
1225	hash_b = dent_b->de_cookie;
1226
1227	if (hash_a > hash_b)
1228	ret = 1;
1229	else if (hash_a < hash_b)
1230	ret = -1;
1231	else {
1232	unsigned int len_a = be16_to_cpu(dent_a->de_name_len);
1233	unsigned int len_b = be16_to_cpu(dent_b->de_name_len);
1234
1235	if (len_a > len_b)
1236	ret = 1;
1237	else if (len_a < len_b)
1238	ret = -1;
1239	else
1240	ret = memcmp(p: dent_a + 1, q: dent_b + 1, size: len_a);
1241	}
1242
1243	return ret;
1244	}
1245
1246	/**
1247	* do_filldir_main - read out directory entries
1248	* @dip: The GFS2 inode
1249	* @ctx: what to feed the entries to
1250	* @darr: an array of struct gfs2_dirent pointers to read
1251	* @entries: the number of entries in darr
1252	* @sort_start: index of the directory array to start our sort
1253	* @copied: pointer to int that's non-zero if a entry has been copied out
1254	*
1255	* Jump through some hoops to make sure that if there are hash collsions,
1256	* they are read out at the beginning of a buffer. We want to minimize
1257	* the possibility that they will fall into different readdir buffers or
1258	* that someone will want to seek to that location.
1259	*
1260	* Returns: errno, >0 if the actor tells you to stop
1261	*/
1262
1263	static int do_filldir_main(struct gfs2_inode *dip, struct dir_context *ctx,
1264	struct gfs2_dirent **darr, u32 entries,
1265	u32 sort_start, int *copied)
1266	{
1267	const struct gfs2_dirent *dent, *dent_next;
1268	u64 off, off_next;
1269	unsigned int x, y;
1270	int run = 0;
1271
1272	if (sort_start < entries)
1273	sort(base: &darr[sort_start], num: entries - sort_start,
1274	size: sizeof(struct gfs2_dirent *), cmp_func: compare_dents, NULL);
1275
1276	dent_next = darr[0];
1277	off_next = dent_next->de_cookie;
1278
1279	for (x = 0, y = 1; x < entries; x++, y++) {
1280	dent = dent_next;
1281	off = off_next;
1282
1283	if (y < entries) {
1284	dent_next = darr[y];
1285	off_next = dent_next->de_cookie;
1286
1287	if (off < ctx->pos)
1288	continue;
1289	ctx->pos = off;
1290
1291	if (off_next == off) {
1292	if (*copied && !run)
1293	return 1;
1294	run = 1;
1295	} else
1296	run = 0;
1297	} else {
1298	if (off < ctx->pos)
1299	continue;
1300	ctx->pos = off;
1301	}
1302
1303	if (!dir_emit(ctx, name: (const char *)(dent + 1),
1304	be16_to_cpu(dent->de_name_len),
1305	be64_to_cpu(dent->de_inum.no_addr),
1306	be16_to_cpu(dent->de_type)))
1307	return 1;
1308
1309	*copied = 1;
1310	}
1311
1312	/* Increment the ctx->pos by one, so the next time we come into the
1313	do_filldir fxn, we get the next entry instead of the last one in the
1314	current leaf */
1315
1316	ctx->pos++;
1317
1318	return 0;
1319	}
1320
1321	static void *gfs2_alloc_sort_buffer(unsigned size)
1322	{
1323	void *ptr = NULL;
1324
1325	if (size < KMALLOC_MAX_SIZE)
1326	ptr = kmalloc(size, GFP_NOFS | __GFP_NOWARN);
1327	if (!ptr)
1328	ptr = __vmalloc(size, GFP_NOFS);
1329	return ptr;
1330	}
1331
1332
1333	static int gfs2_set_cookies(struct gfs2_sbd *sdp, struct buffer_head *bh,
1334	unsigned leaf_nr, struct gfs2_dirent **darr,
1335	unsigned entries)
1336	{
1337	int sort_id = -1;
1338	int i;
1339
1340	for (i = 0; i < entries; i++) {
1341	unsigned offset;
1342
1343	darr[i]->de_cookie = be32_to_cpu(darr[i]->de_hash);
1344	darr[i]->de_cookie = gfs2_disk_hash2offset(darr[i]->de_cookie);
1345
1346	if (!sdp->sd_args.ar_loccookie)
1347	continue;
1348	offset = (char *)(darr[i]) -
1349	(bh->b_data + gfs2_dirent_offset(sdp, buf: bh->b_data));
1350	offset /= GFS2_MIN_DIRENT_SIZE;
1351	offset += leaf_nr * sdp->sd_max_dents_per_leaf;
1352	if (offset >= GFS2_USE_HASH_FLAG ||
1353	leaf_nr >= GFS2_USE_HASH_FLAG) {
1354	darr[i]->de_cookie |= GFS2_USE_HASH_FLAG;
1355	if (sort_id < 0)
1356	sort_id = i;
1357	continue;
1358	}
1359	darr[i]->de_cookie &= GFS2_HASH_INDEX_MASK;
1360	darr[i]->de_cookie |= offset;
1361	}
1362	return sort_id;
1363	}
1364
1365
1366	static int gfs2_dir_read_leaf(struct inode *inode, struct dir_context *ctx,
1367	int *copied, unsigned *depth,
1368	u64 leaf_no)
1369	{
1370	struct gfs2_inode *ip = GFS2_I(inode);
1371	struct gfs2_sbd *sdp = GFS2_SB(inode);
1372	struct buffer_head *bh;
1373	struct gfs2_leaf *lf;
1374	unsigned entries = 0, entries2 = 0;
1375	unsigned leaves = 0, leaf = 0, offset, sort_offset;
1376	struct gfs2_dirent **darr, *dent;
1377	struct dirent_gather g;
1378	struct buffer_head **larr;
1379	int error, i, need_sort = 0, sort_id;
1380	u64 lfn = leaf_no;
1381
1382	do {
1383	error = get_leaf(dip: ip, leaf_no: lfn, bhp: &bh);
1384	if (error)
1385	goto out;
1386	lf = (struct gfs2_leaf *)bh->b_data;
1387	if (leaves == 0)
1388	*depth = be16_to_cpu(lf->lf_depth);
1389	entries += be16_to_cpu(lf->lf_entries);
1390	leaves++;
1391	lfn = be64_to_cpu(lf->lf_next);
1392	brelse(bh);
1393	} while(lfn);
1394
1395	if (*depth < GFS2_DIR_MAX_DEPTH || !sdp->sd_args.ar_loccookie) {
1396	need_sort = 1;
1397	sort_offset = 0;
1398	}
1399
1400	if (!entries)
1401	return 0;
1402
1403	error = -ENOMEM;
1404	/*
1405	* The extra 99 entries are not normally used, but are a buffer
1406	* zone in case the number of entries in the leaf is corrupt.
1407	* 99 is the maximum number of entries that can fit in a single
1408	* leaf block.
1409	*/
1410	larr = gfs2_alloc_sort_buffer(size: (leaves + entries + 99) * sizeof(void *));
1411	if (!larr)
1412	goto out;
1413	darr = (struct gfs2_dirent **)(larr + leaves);
1414	g.pdent = (const struct gfs2_dirent **)darr;
1415	g.offset = 0;
1416	lfn = leaf_no;
1417
1418	do {
1419	error = get_leaf(dip: ip, leaf_no: lfn, bhp: &bh);
1420	if (error)
1421	goto out_free;
1422	lf = (struct gfs2_leaf *)bh->b_data;
1423	lfn = be64_to_cpu(lf->lf_next);
1424	if (lf->lf_entries) {
1425	offset = g.offset;
1426	entries2 += be16_to_cpu(lf->lf_entries);
1427	dent = gfs2_dirent_scan(inode, buf: bh->b_data, len: bh->b_size,
1428	scan: gfs2_dirent_gather, NULL, opaque: &g);
1429	error = PTR_ERR(ptr: dent);
1430	if (IS_ERR(ptr: dent))
1431	goto out_free;
1432	if (entries2 != g.offset) {
1433	fs_warn(sdp, "Number of entries corrupt in dir "
1434	"leaf %llu, entries2 (%u) != "
1435	"g.offset (%u)\n",
1436	(unsigned long long)bh->b_blocknr,
1437	entries2, g.offset);
1438	gfs2_consist_inode(ip);
1439	error = -EIO;
1440	goto out_free;
1441	}
1442	error = 0;
1443	sort_id = gfs2_set_cookies(sdp, bh, leaf_nr: leaf, darr: &darr[offset],
1444	be16_to_cpu(lf->lf_entries));
1445	if (!need_sort && sort_id >= 0) {
1446	need_sort = 1;
1447	sort_offset = offset + sort_id;
1448	}
1449	larr[leaf++] = bh;
1450	} else {
1451	larr[leaf++] = NULL;
1452	brelse(bh);
1453	}
1454	} while(lfn);
1455
1456	BUG_ON(entries2 != entries);
1457	error = do_filldir_main(dip: ip, ctx, darr, entries, sort_start: need_sort ?
1458	sort_offset : entries, copied);
1459	out_free:
1460	for(i = 0; i < leaf; i++)
1461	brelse(bh: larr[i]);
1462	kvfree(addr: larr);
1463	out:
1464	return error;
1465	}
1466
1467	/**
1468	* gfs2_dir_readahead - Issue read-ahead requests for leaf blocks.
1469	* @inode: the directory inode
1470	* @hsize: hash table size
1471	* @index: index into the hash table
1472	* @f_ra: read-ahead parameters
1473	*
1474	* Note: we can't calculate each index like dir_e_read can because we don't
1475	* have the leaf, and therefore we don't have the depth, and therefore we
1476	* don't have the length. So we have to just read enough ahead to make up
1477	* for the loss of information.
1478	*/
1479	static void gfs2_dir_readahead(struct inode *inode, unsigned hsize, u32 index,
1480	struct file_ra_state *f_ra)
1481	{
1482	struct gfs2_inode *ip = GFS2_I(inode);
1483	struct gfs2_glock *gl = ip->i_gl;
1484	struct buffer_head *bh;
1485	u64 blocknr = 0, last;
1486	unsigned count;
1487
1488	/* First check if we've already read-ahead for the whole range. */
1489	if (index + MAX_RA_BLOCKS < f_ra->start)
1490	return;
1491
1492	f_ra->start = max((pgoff_t)index, f_ra->start);
1493	for (count = 0; count < MAX_RA_BLOCKS; count++) {
1494	if (f_ra->start >= hsize) /* if exceeded the hash table */
1495	break;
1496
1497	last = blocknr;
1498	blocknr = be64_to_cpu(ip->i_hash_cache[f_ra->start]);
1499	f_ra->start++;
1500	if (blocknr == last)
1501	continue;
1502
1503	bh = gfs2_getbuf(gl, blkno: blocknr, create: 1);
1504	if (trylock_buffer(bh)) {
1505	if (buffer_uptodate(bh)) {
1506	unlock_buffer(bh);
1507	brelse(bh);
1508	continue;
1509	}
1510	bh->b_end_io = end_buffer_read_sync;
1511	submit_bh(REQ_OP_READ | REQ_RAHEAD | REQ_META |
1512	REQ_PRIO, bh);
1513	continue;
1514	}
1515	brelse(bh);
1516	}
1517	}
1518
1519	/**
1520	* dir_e_read - Reads the entries from a directory into a filldir buffer
1521	* @inode: the directory inode
1522	* @ctx: actor to feed the entries to
1523	* @f_ra: read-ahead parameters
1524	*
1525	* Returns: errno
1526	*/
1527
1528	static int dir_e_read(struct inode *inode, struct dir_context *ctx,
1529	struct file_ra_state *f_ra)
1530	{
1531	struct gfs2_inode *dip = GFS2_I(inode);
1532	u32 hsize, len = 0;
1533	u32 hash, index;
1534	__be64 *lp;
1535	int copied = 0;
1536	int error = 0;
1537	unsigned depth = 0;
1538
1539	hsize = BIT(dip->i_depth);
1540	hash = gfs2_dir_offset2hash(ctx->pos);
1541	index = hash >> (32 - dip->i_depth);
1542
1543	if (dip->i_hash_cache == NULL)
1544	f_ra->start = 0;
1545	lp = gfs2_dir_get_hash_table(ip: dip);
1546	if (IS_ERR(ptr: lp))
1547	return PTR_ERR(ptr: lp);
1548
1549	gfs2_dir_readahead(inode, hsize, index, f_ra);
1550
1551	while (index < hsize) {
1552	error = gfs2_dir_read_leaf(inode, ctx,
1553	copied: &copied, depth: &depth,
1554	be64_to_cpu(lp[index]));
1555	if (error)
1556	break;
1557
1558	len = BIT(dip->i_depth - depth);
1559	index = (index & ~(len - 1)) + len;
1560	}
1561
1562	if (error > 0)
1563	error = 0;
1564	return error;
1565	}
1566
1567	int gfs2_dir_read(struct inode *inode, struct dir_context *ctx,
1568	struct file_ra_state *f_ra)
1569	{
1570	struct gfs2_inode *dip = GFS2_I(inode);
1571	struct gfs2_sbd *sdp = GFS2_SB(inode);
1572	struct dirent_gather g;
1573	struct gfs2_dirent **darr, *dent;
1574	struct buffer_head *dibh;
1575	int copied = 0;
1576	int error;
1577
1578	if (!dip->i_entries)
1579	return 0;
1580
1581	if (dip->i_diskflags & GFS2_DIF_EXHASH)
1582	return dir_e_read(inode, ctx, f_ra);
1583
1584	if (!gfs2_is_stuffed(ip: dip)) {
1585	gfs2_consist_inode(dip);
1586	return -EIO;
1587	}
1588
1589	error = gfs2_meta_inode_buffer(ip: dip, bhp: &dibh);
1590	if (error)
1591	return error;
1592
1593	error = -ENOMEM;
1594	/* 96 is max number of dirents which can be stuffed into an inode */
1595	darr = kmalloc_array(n: 96, size: sizeof(struct gfs2_dirent *), GFP_NOFS);
1596	if (darr) {
1597	g.pdent = (const struct gfs2_dirent **)darr;
1598	g.offset = 0;
1599	dent = gfs2_dirent_scan(inode, buf: dibh->b_data, len: dibh->b_size,
1600	scan: gfs2_dirent_gather, NULL, opaque: &g);
1601	if (IS_ERR(ptr: dent)) {
1602	error = PTR_ERR(ptr: dent);
1603	goto out;
1604	}
1605	if (dip->i_entries != g.offset) {
1606	fs_warn(sdp, "Number of entries corrupt in dir %llu, "
1607	"ip->i_entries (%u) != g.offset (%u)\n",
1608	(unsigned long long)dip->i_no_addr,
1609	dip->i_entries,
1610	g.offset);
1611	gfs2_consist_inode(dip);
1612	error = -EIO;
1613	goto out;
1614	}
1615	gfs2_set_cookies(sdp, bh: dibh, leaf_nr: 0, darr, entries: dip->i_entries);
1616	error = do_filldir_main(dip, ctx, darr,
1617	entries: dip->i_entries, sort_start: 0, copied: &copied);
1618	out:
1619	kfree(objp: darr);
1620	}
1621
1622	if (error > 0)
1623	error = 0;
1624
1625	brelse(bh: dibh);
1626
1627	return error;
1628	}
1629
1630	/**
1631	* gfs2_dir_search - Search a directory
1632	* @dir: The GFS2 directory inode
1633	* @name: The name we are looking up
1634	* @fail_on_exist: Fail if the name exists rather than looking it up
1635	*
1636	* This routine searches a directory for a file or another directory.
1637	* Assumes a glock is held on dip.
1638	*
1639	* Returns: errno
1640	*/
1641
1642	struct inode *gfs2_dir_search(struct inode *dir, const struct qstr *name,
1643	bool fail_on_exist)
1644	{
1645	struct buffer_head *bh;
1646	struct gfs2_dirent *dent;
1647	u64 addr, formal_ino;
1648	u16 dtype;
1649
1650	dent = gfs2_dirent_search(inode: dir, name, scan: gfs2_dirent_find, pbh: &bh);
1651	if (dent) {
1652	struct inode *inode;
1653	u16 rahead;
1654
1655	if (IS_ERR(ptr: dent))
1656	return ERR_CAST(ptr: dent);
1657	dtype = be16_to_cpu(dent->de_type);
1658	rahead = be16_to_cpu(dent->de_rahead);
1659	addr = be64_to_cpu(dent->de_inum.no_addr);
1660	formal_ino = be64_to_cpu(dent->de_inum.no_formal_ino);
1661	brelse(bh);
1662	if (fail_on_exist)
1663	return ERR_PTR(error: -EEXIST);
1664	inode = gfs2_inode_lookup(sb: dir->i_sb, type: dtype, no_addr: addr, no_formal_ino: formal_ino,
1665	GFS2_BLKST_FREE /* ignore */);
1666	if (!IS_ERR(ptr: inode))
1667	GFS2_I(inode)->i_rahead = rahead;
1668	return inode;
1669	}
1670	return ERR_PTR(error: -ENOENT);
1671	}
1672
1673	int gfs2_dir_check(struct inode *dir, const struct qstr *name,
1674	const struct gfs2_inode *ip)
1675	{
1676	struct buffer_head *bh;
1677	struct gfs2_dirent *dent;
1678	int ret = -ENOENT;
1679
1680	dent = gfs2_dirent_search(inode: dir, name, scan: gfs2_dirent_find, pbh: &bh);
1681	if (dent) {
1682	if (IS_ERR(ptr: dent))
1683	return PTR_ERR(ptr: dent);
1684	if (ip) {
1685	if (be64_to_cpu(dent->de_inum.no_addr) != ip->i_no_addr)
1686	goto out;
1687	if (be64_to_cpu(dent->de_inum.no_formal_ino) !=
1688	ip->i_no_formal_ino)
1689	goto out;
1690	if (unlikely(IF2DT(ip->i_inode.i_mode) !=
1691	be16_to_cpu(dent->de_type))) {
1692	gfs2_consist_inode(GFS2_I(dir));
1693	ret = -EIO;
1694	goto out;
1695	}
1696	}
1697	ret = 0;
1698	out:
1699	brelse(bh);
1700	}
1701	return ret;
1702	}
1703
1704	/**
1705	* dir_new_leaf - Add a new leaf onto hash chain
1706	* @inode: The directory
1707	* @name: The name we are adding
1708	*
1709	* This adds a new dir leaf onto an existing leaf when there is not
1710	* enough space to add a new dir entry. This is a last resort after
1711	* we've expanded the hash table to max size and also split existing
1712	* leaf blocks, so it will only occur for very large directories.
1713	*
1714	* The dist parameter is set to 1 for leaf blocks directly attached
1715	* to the hash table, 2 for one layer of indirection, 3 for two layers
1716	* etc. We are thus able to tell the difference between an old leaf
1717	* with dist set to zero (i.e. "don't know") and a new one where we
1718	* set this information for debug/fsck purposes.
1719	*
1720	* Returns: 0 on success, or -ve on error
1721	*/
1722
1723	static int dir_new_leaf(struct inode *inode, const struct qstr *name)
1724	{
1725	struct buffer_head *bh, *obh;
1726	struct gfs2_inode *ip = GFS2_I(inode);
1727	struct gfs2_leaf *leaf, *oleaf;
1728	u32 dist = 1;
1729	int error;
1730	u32 index;
1731	u64 bn;
1732
1733	index = name->hash >> (32 - ip->i_depth);
1734	error = get_first_leaf(dip: ip, index, bh_out: &obh);
1735	if (error)
1736	return error;
1737	do {
1738	dist++;
1739	oleaf = (struct gfs2_leaf *)obh->b_data;
1740	bn = be64_to_cpu(oleaf->lf_next);
1741	if (!bn)
1742	break;
1743	brelse(bh: obh);
1744	error = get_leaf(dip: ip, leaf_no: bn, bhp: &obh);
1745	if (error)
1746	return error;
1747	} while(1);
1748
1749	gfs2_trans_add_meta(gl: ip->i_gl, bh: obh);
1750
1751	leaf = new_leaf(inode, pbh: &bh, be16_to_cpu(oleaf->lf_depth));
1752	if (!leaf) {
1753	brelse(bh: obh);
1754	return -ENOSPC;
1755	}
1756	leaf->lf_dist = cpu_to_be32(dist);
1757	oleaf->lf_next = cpu_to_be64(bh->b_blocknr);
1758	brelse(bh);
1759	brelse(bh: obh);
1760
1761	error = gfs2_meta_inode_buffer(ip, bhp: &bh);
1762	if (error)
1763	return error;
1764	gfs2_trans_add_meta(gl: ip->i_gl, bh);
1765	gfs2_add_inode_blocks(inode: &ip->i_inode, change: 1);
1766	gfs2_dinode_out(ip, buf: bh->b_data);
1767	brelse(bh);
1768	return 0;
1769	}
1770
1771	static u16 gfs2_inode_ra_len(const struct gfs2_inode *ip)
1772	{
1773	u64 where = ip->i_no_addr + 1;
1774	if (ip->i_eattr == where)
1775	return 1;
1776	return 0;
1777	}
1778
1779	/**
1780	* gfs2_dir_add - Add new filename into directory
1781	* @inode: The directory inode
1782	* @name: The new name
1783	* @nip: The GFS2 inode to be linked in to the directory
1784	* @da: The directory addition info
1785	*
1786	* If the call to gfs2_diradd_alloc_required resulted in there being
1787	* no need to allocate any new directory blocks, then it will contain
1788	* a pointer to the directory entry and the bh in which it resides. We
1789	* can use that without having to repeat the search. If there was no
1790	* free space, then we must now create more space.
1791	*
1792	* Returns: 0 on success, error code on failure
1793	*/
1794
1795	int gfs2_dir_add(struct inode *inode, const struct qstr *name,
1796	const struct gfs2_inode *nip, struct gfs2_diradd *da)
1797	{
1798	struct gfs2_inode *ip = GFS2_I(inode);
1799	struct buffer_head *bh = da->bh;
1800	struct gfs2_dirent *dent = da->dent;
1801	struct timespec64 tv;
1802	struct gfs2_leaf *leaf;
1803	int error;
1804
1805	while(1) {
1806	if (da->bh == NULL) {
1807	dent = gfs2_dirent_search(inode, name,
1808	scan: gfs2_dirent_find_space, pbh: &bh);
1809	}
1810	if (dent) {
1811	if (IS_ERR(ptr: dent))
1812	return PTR_ERR(ptr: dent);
1813	dent = gfs2_init_dirent(inode, dent, name, bh);
1814	gfs2_inum_out(ip: nip, dent);
1815	dent->de_type = cpu_to_be16(IF2DT(nip->i_inode.i_mode));
1816	dent->de_rahead = cpu_to_be16(gfs2_inode_ra_len(nip));
1817	tv = inode_set_ctime_current(inode: &ip->i_inode);
1818	if (ip->i_diskflags & GFS2_DIF_EXHASH) {
1819	leaf = (struct gfs2_leaf *)bh->b_data;
1820	be16_add_cpu(var: &leaf->lf_entries, val: 1);
1821	leaf->lf_nsec = cpu_to_be32(tv.tv_nsec);
1822	leaf->lf_sec = cpu_to_be64(tv.tv_sec);
1823	}
1824	da->dent = NULL;
1825	da->bh = NULL;
1826	brelse(bh);
1827	ip->i_entries++;
1828	inode_set_mtime_to_ts(inode: &ip->i_inode, ts: tv);
1829	if (S_ISDIR(nip->i_inode.i_mode))
1830	inc_nlink(inode: &ip->i_inode);
1831	mark_inode_dirty(inode);
1832	error = 0;
1833	break;
1834	}
1835	if (!(ip->i_diskflags & GFS2_DIF_EXHASH)) {
1836	error = dir_make_exhash(inode);
1837	if (error)
1838	break;
1839	continue;
1840	}
1841	error = dir_split_leaf(inode, name);
1842	if (error == 0)
1843	continue;
1844	if (error < 0)
1845	break;
1846	if (ip->i_depth < GFS2_DIR_MAX_DEPTH) {
1847	error = dir_double_exhash(dip: ip);
1848	if (error)
1849	break;
1850	error = dir_split_leaf(inode, name);
1851	if (error < 0)
1852	break;
1853	if (error == 0)
1854	continue;
1855	}
1856	error = dir_new_leaf(inode, name);
1857	if (!error)
1858	continue;
1859	error = -ENOSPC;
1860	break;
1861	}
1862	return error;
1863	}
1864
1865
1866	/**
1867	* gfs2_dir_del - Delete a directory entry
1868	* @dip: The GFS2 inode
1869	* @dentry: The directory entry we want to delete
1870	*
1871	* Returns: 0 on success, error code on failure
1872	*/
1873
1874	int gfs2_dir_del(struct gfs2_inode *dip, const struct dentry *dentry)
1875	{
1876	const struct qstr *name = &dentry->d_name;
1877	struct gfs2_dirent *dent, *prev = NULL;
1878	struct buffer_head *bh;
1879	struct timespec64 tv;
1880
1881	/* Returns _either_ the entry (if its first in block) or the
1882	previous entry otherwise */
1883	dent = gfs2_dirent_search(inode: &dip->i_inode, name, scan: gfs2_dirent_prev, pbh: &bh);
1884	if (!dent) {
1885	gfs2_consist_inode(dip);
1886	return -EIO;
1887	}
1888	if (IS_ERR(ptr: dent)) {
1889	gfs2_consist_inode(dip);
1890	return PTR_ERR(ptr: dent);
1891	}
1892	/* If not first in block, adjust pointers accordingly */
1893	if (gfs2_dirent_find(dent, name, NULL) == 0) {
1894	prev = dent;
1895	dent = (struct gfs2_dirent *)((char *)dent + be16_to_cpu(prev->de_rec_len));
1896	}
1897
1898	dirent_del(dip, bh, prev, cur: dent);
1899	tv = inode_set_ctime_current(inode: &dip->i_inode);
1900	if (dip->i_diskflags & GFS2_DIF_EXHASH) {
1901	struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data;
1902	u16 entries = be16_to_cpu(leaf->lf_entries);
1903	if (!entries)
1904	gfs2_consist_inode(dip);
1905	leaf->lf_entries = cpu_to_be16(--entries);
1906	leaf->lf_nsec = cpu_to_be32(tv.tv_nsec);
1907	leaf->lf_sec = cpu_to_be64(tv.tv_sec);
1908	}
1909	brelse(bh);
1910
1911	if (!dip->i_entries)
1912	gfs2_consist_inode(dip);
1913	dip->i_entries--;
1914	inode_set_mtime_to_ts(inode: &dip->i_inode, ts: tv);
1915	if (d_is_dir(dentry))
1916	drop_nlink(inode: &dip->i_inode);
1917	mark_inode_dirty(inode: &dip->i_inode);
1918
1919	return 0;
1920	}
1921
1922	/**
1923	* gfs2_dir_mvino - Change inode number of directory entry
1924	* @dip: The GFS2 directory inode
1925	* @filename: the filename to be moved
1926	* @nip: the new GFS2 inode
1927	* @new_type: the de_type of the new dirent
1928	*
1929	* This routine changes the inode number of a directory entry. It's used
1930	* by rename to change ".." when a directory is moved.
1931	* Assumes a glock is held on dvp.
1932	*
1933	* Returns: errno
1934	*/
1935
1936	int gfs2_dir_mvino(struct gfs2_inode *dip, const struct qstr *filename,
1937	const struct gfs2_inode *nip, unsigned int new_type)
1938	{
1939	struct buffer_head *bh;
1940	struct gfs2_dirent *dent;
1941
1942	dent = gfs2_dirent_search(inode: &dip->i_inode, name: filename, scan: gfs2_dirent_find, pbh: &bh);
1943	if (!dent) {
1944	gfs2_consist_inode(dip);
1945	return -EIO;
1946	}
1947	if (IS_ERR(ptr: dent))
1948	return PTR_ERR(ptr: dent);
1949
1950	gfs2_trans_add_meta(gl: dip->i_gl, bh);
1951	gfs2_inum_out(ip: nip, dent);
1952	dent->de_type = cpu_to_be16(new_type);
1953	brelse(bh);
1954
1955	inode_set_mtime_to_ts(inode: &dip->i_inode, ts: inode_set_ctime_current(inode: &dip->i_inode));
1956	mark_inode_dirty_sync(inode: &dip->i_inode);
1957	return 0;
1958	}
1959
1960	/**
1961	* leaf_dealloc - Deallocate a directory leaf
1962	* @dip: the directory
1963	* @index: the hash table offset in the directory
1964	* @len: the number of pointers to this leaf
1965	* @leaf_no: the leaf number
1966	* @leaf_bh: buffer_head for the starting leaf
1967	* @last_dealloc: 1 if this is the final dealloc for the leaf, else 0
1968	*
1969	* Returns: errno
1970	*/
1971
1972	static int leaf_dealloc(struct gfs2_inode *dip, u32 index, u32 len,
1973	u64 leaf_no, struct buffer_head *leaf_bh,
1974	int last_dealloc)
1975	{
1976	struct gfs2_sbd *sdp = GFS2_SB(inode: &dip->i_inode);
1977	struct gfs2_leaf *tmp_leaf;
1978	struct gfs2_rgrp_list rlist;
1979	struct buffer_head *bh, *dibh;
1980	u64 blk, nblk;
1981	unsigned int rg_blocks = 0, l_blocks = 0;
1982	char *ht;
1983	unsigned int x, size = len * sizeof(u64);
1984	int error;
1985
1986	error = gfs2_rindex_update(sdp);
1987	if (error)
1988	return error;
1989
1990	memset(&rlist, 0, sizeof(struct gfs2_rgrp_list));
1991
1992	ht = kzalloc(size, GFP_NOFS | __GFP_NOWARN);
1993	if (ht == NULL)
1994	ht = __vmalloc(size, GFP_NOFS | __GFP_NOWARN | __GFP_ZERO);
1995	if (!ht)
1996	return -ENOMEM;
1997
1998	error = gfs2_quota_hold(ip: dip, NO_UID_QUOTA_CHANGE, NO_GID_QUOTA_CHANGE);
1999	if (error)
2000	goto out;
2001
2002	/* Count the number of leaves */
2003	bh = leaf_bh;
2004
2005	for (blk = leaf_no; blk; blk = nblk) {
2006	if (blk != leaf_no) {
2007	error = get_leaf(dip, leaf_no: blk, bhp: &bh);
2008	if (error)
2009	goto out_rlist;
2010	}
2011	tmp_leaf = (struct gfs2_leaf *)bh->b_data;
2012	nblk = be64_to_cpu(tmp_leaf->lf_next);
2013	if (blk != leaf_no)
2014	brelse(bh);
2015
2016	gfs2_rlist_add(ip: dip, rlist: &rlist, block: blk);
2017	l_blocks++;
2018	}
2019
2020	gfs2_rlist_alloc(rlist: &rlist, LM_ST_EXCLUSIVE, LM_FLAG_NODE_SCOPE);
2021
2022	for (x = 0; x < rlist.rl_rgrps; x++) {
2023	struct gfs2_rgrpd *rgd = gfs2_glock2rgrp(gl: rlist.rl_ghs[x].gh_gl);
2024
2025	rg_blocks += rgd->rd_length;
2026	}
2027
2028	error = gfs2_glock_nq_m(num_gh: rlist.rl_rgrps, ghs: rlist.rl_ghs);
2029	if (error)
2030	goto out_rlist;
2031
2032	error = gfs2_trans_begin(sdp,
2033	blocks: rg_blocks + (DIV_ROUND_UP(size, sdp->sd_jbsize) + 1) +
2034	RES_DINODE + RES_STATFS + RES_QUOTA, RES_DINODE +
2035	l_blocks);
2036	if (error)
2037	goto out_rg_gunlock;
2038
2039	bh = leaf_bh;
2040
2041	for (blk = leaf_no; blk; blk = nblk) {
2042	struct gfs2_rgrpd *rgd;
2043
2044	if (blk != leaf_no) {
2045	error = get_leaf(dip, leaf_no: blk, bhp: &bh);
2046	if (error)
2047	goto out_end_trans;
2048	}
2049	tmp_leaf = (struct gfs2_leaf *)bh->b_data;
2050	nblk = be64_to_cpu(tmp_leaf->lf_next);
2051	if (blk != leaf_no)
2052	brelse(bh);
2053
2054	rgd = gfs2_blk2rgrpd(sdp, blk, exact: true);
2055	gfs2_free_meta(ip: dip, rgd, bstart: blk, blen: 1);
2056	gfs2_add_inode_blocks(inode: &dip->i_inode, change: -1);
2057	}
2058
2059	error = gfs2_dir_write_data(ip: dip, buf: ht, offset: index * sizeof(u64), size);
2060	if (error != size) {
2061	if (error >= 0)
2062	error = -EIO;
2063	goto out_end_trans;
2064	}
2065
2066	error = gfs2_meta_inode_buffer(ip: dip, bhp: &dibh);
2067	if (error)
2068	goto out_end_trans;
2069
2070	gfs2_trans_add_meta(gl: dip->i_gl, bh: dibh);
2071	/* On the last dealloc, make this a regular file in case we crash.
2072	(We don't want to free these blocks a second time.) */
2073	if (last_dealloc)
2074	dip->i_inode.i_mode = S_IFREG;
2075	gfs2_dinode_out(ip: dip, buf: dibh->b_data);
2076	brelse(bh: dibh);
2077
2078	out_end_trans:
2079	gfs2_trans_end(sdp);
2080	out_rg_gunlock:
2081	gfs2_glock_dq_m(num_gh: rlist.rl_rgrps, ghs: rlist.rl_ghs);
2082	out_rlist:
2083	gfs2_rlist_free(rlist: &rlist);
2084	gfs2_quota_unhold(ip: dip);
2085	out:
2086	kvfree(addr: ht);
2087	return error;
2088	}
2089
2090	/**
2091	* gfs2_dir_exhash_dealloc - free all the leaf blocks in a directory
2092	* @dip: the directory
2093	*
2094	* Dealloc all on-disk directory leaves to FREEMETA state
2095	* Change on-disk inode type to "regular file"
2096	*
2097	* Returns: errno
2098	*/
2099
2100	int gfs2_dir_exhash_dealloc(struct gfs2_inode *dip)
2101	{
2102	struct buffer_head *bh;
2103	struct gfs2_leaf *leaf;
2104	u32 hsize, len;
2105	u32 index = 0, next_index;
2106	__be64 *lp;
2107	u64 leaf_no;
2108	int error = 0, last;
2109
2110	hsize = BIT(dip->i_depth);
2111
2112	lp = gfs2_dir_get_hash_table(ip: dip);
2113	if (IS_ERR(ptr: lp))
2114	return PTR_ERR(ptr: lp);
2115
2116	while (index < hsize) {
2117	leaf_no = be64_to_cpu(lp[index]);
2118	if (leaf_no) {
2119	error = get_leaf(dip, leaf_no, bhp: &bh);
2120	if (error)
2121	goto out;
2122	leaf = (struct gfs2_leaf *)bh->b_data;
2123	len = BIT(dip->i_depth - be16_to_cpu(leaf->lf_depth));
2124
2125	next_index = (index & ~(len - 1)) + len;
2126	last = ((next_index >= hsize) ? 1 : 0);
2127	error = leaf_dealloc(dip, index, len, leaf_no, leaf_bh: bh,
2128	last_dealloc: last);
2129	brelse(bh);
2130	if (error)
2131	goto out;
2132	index = next_index;
2133	} else
2134	index++;
2135	}
2136
2137	if (index != hsize) {
2138	gfs2_consist_inode(dip);
2139	error = -EIO;
2140	}
2141
2142	out:
2143
2144	return error;
2145	}
2146
2147	/**
2148	* gfs2_diradd_alloc_required - find if adding entry will require an allocation
2149	* @inode: the directory inode being written to
2150	* @name: the filename that's going to be added
2151	* @da: The structure to return dir alloc info
2152	*
2153	* Returns: 0 if ok, -ve on error
2154	*/
2155
2156	int gfs2_diradd_alloc_required(struct inode *inode, const struct qstr *name,
2157	struct gfs2_diradd *da)
2158	{
2159	struct gfs2_inode *ip = GFS2_I(inode);
2160	struct gfs2_sbd *sdp = GFS2_SB(inode);
2161	const unsigned int extra = sizeof(struct gfs2_dinode) - sizeof(struct gfs2_leaf);
2162	struct gfs2_dirent *dent;
2163	struct buffer_head *bh;
2164
2165	da->nr_blocks = 0;
2166	da->bh = NULL;
2167	da->dent = NULL;
2168
2169	dent = gfs2_dirent_search(inode, name, scan: gfs2_dirent_find_space, pbh: &bh);
2170	if (!dent) {
2171	da->nr_blocks = sdp->sd_max_dirres;
2172	if (!(ip->i_diskflags & GFS2_DIF_EXHASH) &&
2173	(GFS2_DIRENT_SIZE(name->len) < extra))
2174	da->nr_blocks = 1;
2175	return 0;
2176	}
2177	if (IS_ERR(ptr: dent))
2178	return PTR_ERR(ptr: dent);
2179
2180	if (da->save_loc) {
2181	da->bh = bh;
2182	da->dent = dent;
2183	} else {
2184	brelse(bh);
2185	}
2186	return 0;
2187	}
2188
2189