1 /*
2  * Copyright (c) 2011-2012 The DragonFly Project.  All rights reserved.
3  *
4  * This code is derived from software contributed to The DragonFly Project
5  * by Matthew Dillon <dillon@dragonflybsd.org>
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  * 3. Neither the name of The DragonFly Project nor the names of its
18  *    contributors may be used to endorse or promote products derived
19  *    from this software without specific, prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  */
34 
35 #include <sys/types.h>
36 #include <sys/diskslice.h>
37 #include <sys/diskmbr.h>
38 #include <sys/stat.h>
39 #include <sys/time.h>
40 #include <sys/sysctl.h>
41 #include <vfs/hammer2/hammer2_disk.h>
42 
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <stdarg.h>
46 #include <stddef.h>
47 #include <unistd.h>
48 #include <string.h>
49 #include <errno.h>
50 #include <fcntl.h>
51 #include <assert.h>
52 #include <err.h>
53 #include <uuid.h>
54 
55 #define hammer2_icrc32(buf, size)	iscsi_crc32((buf), (size))
56 #define hammer2_icrc32c(buf, size, crc)	iscsi_crc32_ext((buf), (size), (crc))
57 uint32_t iscsi_crc32(const void *buf, size_t size);
58 uint32_t iscsi_crc32_ext(const void *buf, size_t size, uint32_t ocrc);
59 
60 static hammer2_off_t check_volume(const char *path, int *fdp);
61 static int64_t getsize(const char *str, int64_t minval, int64_t maxval, int pw);
62 static const char *sizetostr(hammer2_off_t size);
63 static uint64_t nowtime(void);
64 static void usage(void);
65 
66 static void format_hammer2(int fd, hammer2_off_t total_space,
67 				hammer2_off_t free_space);
68 static void alloc_direct(hammer2_off_t *basep, hammer2_blockref_t *bref,
69 				size_t bytes);
70 static hammer2_key_t dirhash(const unsigned char *name, size_t len);
71 
72 static int Hammer2Version = -1;
73 static int ForceOpt = 0;
74 static uuid_t Hammer2_FSType;	/* static filesystem type id for HAMMER2 */
75 static uuid_t Hammer2_FSId;	/* unique filesystem id in volu header */
76 static uuid_t Hammer2_SPFSId;	/* PFS id in super-root inode */
77 static uuid_t Hammer2_RPFSId;	/* PFS id in root inode */
78 static const char *Label = "ROOT";
79 static hammer2_off_t BootAreaSize;
80 static hammer2_off_t AuxAreaSize;
81 
82 #define GIG	((hammer2_off_t)1024*1024*1024)
83 
84 int
85 main(int ac, char **av)
86 {
87 	uint32_t status;
88 	hammer2_off_t total_space;
89 	hammer2_off_t free_space;
90 	hammer2_off_t reserved_space;
91 	int ch;
92 	int fd = -1;
93 	char *fsidstr;
94 	char *spfsidstr;
95 	char *rpfsidstr;
96 
97 	/*
98 	 * Sanity check basic filesystem structures.  No cookies for us
99 	 * if it gets broken!
100 	 */
101 	assert(sizeof(hammer2_volume_data_t) == HAMMER2_VOLUME_BYTES);
102 	assert(sizeof(hammer2_inode_data_t) == HAMMER2_INODE_BYTES);
103 	assert(sizeof(hammer2_blockref_t) == HAMMER2_BLOCKREF_BYTES);
104 
105 	/*
106 	 * Generate a filesystem id and lookup the filesystem type
107 	 */
108 	srandomdev();
109 	uuidgen(&Hammer2_FSId, 1);
110 	uuidgen(&Hammer2_SPFSId, 1);
111 	uuidgen(&Hammer2_RPFSId, 1);
112 	uuid_from_string(HAMMER2_UUID_STRING, &Hammer2_FSType, &status);
113 	/*uuid_name_lookup(&Hammer2_FSType, "DragonFly HAMMER2", &status);*/
114 	if (status != uuid_s_ok) {
115 		errx(1, "uuids file does not have the DragonFly "
116 			"HAMMER filesystem type");
117 	}
118 
119 	/*
120 	 * Parse arguments
121 	 */
122 	while ((ch = getopt(ac, av, "fL:b:m:r:V:")) != -1) {
123 		switch(ch) {
124 		case 'f':
125 			ForceOpt = 1;
126 			break;
127 		case 'L':
128 			Label = optarg;
129 			if (strlen(Label) > HAMMER2_INODE_MAXNAME) {
130 				errx(1, "Root directory label too long "
131 					"(64 chars max)\n");
132 			}
133 			break;
134 		case 'b':
135 			BootAreaSize = getsize(optarg,
136 					 HAMMER2_NEWFS_ALIGN,
137 					 HAMMER2_BOOT_MAX_BYTES, 2);
138 			break;
139 		case 'r':
140 			AuxAreaSize = getsize(optarg,
141 					 HAMMER2_NEWFS_ALIGN,
142 					 HAMMER2_REDO_MAX_BYTES, 2);
143 			break;
144 		case 'V':
145 			Hammer2Version = strtol(optarg, NULL, 0);
146 			if (Hammer2Version < HAMMER2_VOL_VERSION_MIN ||
147 			    Hammer2Version >= HAMMER2_VOL_VERSION_WIP) {
148 				errx(1,
149 				     "I don't understand how to format "
150 				     "HAMMER2 version %d\n",
151 				     Hammer2Version);
152 			}
153 			break;
154 		default:
155 			usage();
156 			break;
157 		}
158 	}
159 
160 	if (Hammer2Version < 0) {
161 		size_t olen = sizeof(Hammer2Version);
162 		Hammer2Version = HAMMER2_VOL_VERSION_DEFAULT;
163 		if (sysctlbyname("vfs.hammer2.supported_version",
164 				 &Hammer2Version, &olen, NULL, 0) == 0) {
165 			if (Hammer2Version >= HAMMER2_VOL_VERSION_WIP) {
166 				Hammer2Version = HAMMER2_VOL_VERSION_WIP - 1;
167 				fprintf(stderr,
168 					"newfs_hammer: WARNING: HAMMER2 VFS "
169 					"supports higher version than I "
170 					"understand,\n"
171 					"using version %d\n",
172 					Hammer2Version);
173 			}
174 		} else {
175 			fprintf(stderr,
176 				"newfs_hammer: WARNING: HAMMER2 VFS not "
177 				"loaded, cannot get version info.\n"
178 				"Using version %d\n",
179 				HAMMER2_VOL_VERSION_DEFAULT);
180 		}
181 	}
182 
183 	/*
184 	 * Collect volume information.
185 	 */
186 	ac -= optind;
187 	av += optind;
188 
189 	if (ac != 1) {
190 		fprintf(stderr, "Exactly one disk device must be specified\n");
191 		exit(1);
192 	}
193 	total_space = check_volume(av[0], &fd);
194 
195 	/*
196 	 * ~typically 8MB alignment to avoid edge cases for reserved blocks
197 	 * and so raid stripes (if any) operate efficiently.
198 	 */
199 	total_space &= ~HAMMER2_VOLUME_ALIGNMASK64;
200 
201 	/*
202 	 * Calculate defaults for the boot area size and round to the
203 	 * volume alignment boundary.
204 	 */
205 	if (BootAreaSize == 0) {
206 		BootAreaSize = HAMMER2_BOOT_NOM_BYTES;
207 		while (BootAreaSize > total_space / 20)
208 			BootAreaSize >>= 1;
209 		if (BootAreaSize < HAMMER2_BOOT_MIN_BYTES)
210 			BootAreaSize = HAMMER2_BOOT_MIN_BYTES;
211 	} else if (BootAreaSize < HAMMER2_BOOT_MIN_BYTES) {
212 		BootAreaSize = HAMMER2_BOOT_MIN_BYTES;
213 	}
214 	BootAreaSize = (BootAreaSize + HAMMER2_VOLUME_ALIGNMASK64) &
215 		       ~HAMMER2_VOLUME_ALIGNMASK64;
216 
217 	/*
218 	 * Calculate defaults for the redo area size and round to the
219 	 * volume alignment boundary.
220 	 */
221 	if (AuxAreaSize == 0) {
222 		AuxAreaSize = HAMMER2_REDO_NOM_BYTES;
223 		while (AuxAreaSize > total_space / 20)
224 			AuxAreaSize >>= 1;
225 		if (AuxAreaSize < HAMMER2_REDO_MIN_BYTES)
226 			AuxAreaSize = HAMMER2_REDO_MIN_BYTES;
227 	} else if (AuxAreaSize < HAMMER2_REDO_MIN_BYTES) {
228 		AuxAreaSize = HAMMER2_REDO_MIN_BYTES;
229 	}
230 	AuxAreaSize = (AuxAreaSize + HAMMER2_VOLUME_ALIGNMASK64) &
231 		       ~HAMMER2_VOLUME_ALIGNMASK64;
232 
233 	/*
234 	 * We'll need to stuff this in the volume header soon.
235 	 */
236 	uuid_to_string(&Hammer2_FSId, &fsidstr, &status);
237 	uuid_to_string(&Hammer2_SPFSId, &spfsidstr, &status);
238 	uuid_to_string(&Hammer2_RPFSId, &rpfsidstr, &status);
239 
240 	/*
241 	 * Calculate the amount of reserved space.  HAMMER2_ZONE_SEG (4MB)
242 	 * is reserved at the beginning of every 2GB of storage, rounded up.
243 	 * Thus a 200MB filesystem will still have a 4MB reserve area.
244 	 *
245 	 * We also include the boot and redo areas in the reserve.  The
246 	 * reserve is used to help 'df' calculate the amount of available
247 	 * space.
248 	 */
249 	reserved_space = ((total_space + HAMMER2_ZONE_MASK64) /
250 			  HAMMER2_ZONE_BYTES64) * HAMMER2_ZONE_SEG64;
251 
252 	free_space = total_space - reserved_space -
253 		     BootAreaSize - AuxAreaSize;
254 
255 	format_hammer2(fd, total_space, free_space);
256 	fsync(fd);
257 	close(fd);
258 
259 	printf("---------------------------------------------\n");
260 	printf("total-size:       %s (%jd bytes)\n",
261 	       sizetostr(total_space),
262 	       (intmax_t)total_space);
263 	printf("root-label:       %s\n", Label);
264 	printf("version:            %d\n", Hammer2Version);
265 	printf("boot-area-size:   %s\n", sizetostr(BootAreaSize));
266 	printf("aux-area-size:    %s\n", sizetostr(AuxAreaSize));
267 	printf("topo-reserved:	  %s\n", sizetostr(reserved_space));
268 	printf("free-space:       %s\n", sizetostr(free_space));
269 	printf("fsid:             %s\n", fsidstr);
270 	printf("supr-pfsid:       %s\n", spfsidstr);
271 	printf("root-pfsid:       %s\n", rpfsidstr);
272 	printf("\n");
273 
274 	return(0);
275 }
276 
277 static
278 void
279 usage(void)
280 {
281 	fprintf(stderr,
282 		"usage: newfs_hammer -L label [-f] [-b bootsize] "
283 		"[-r redosize] [-V version] special ...\n"
284 	);
285 	exit(1);
286 }
287 
288 /*
289  * Convert the size in bytes to a human readable string.
290  */
291 static
292 const char *
293 sizetostr(hammer2_off_t size)
294 {
295 	static char buf[32];
296 
297 	if (size < 1024 / 2) {
298 		snprintf(buf, sizeof(buf), "%6.2f", (double)size);
299 	} else if (size < 1024 * 1024 / 2) {
300 		snprintf(buf, sizeof(buf), "%6.2fKB",
301 			(double)size / 1024);
302 	} else if (size < 1024 * 1024 * 1024LL / 2) {
303 		snprintf(buf, sizeof(buf), "%6.2fMB",
304 			(double)size / (1024 * 1024));
305 	} else if (size < 1024 * 1024 * 1024LL * 1024LL / 2) {
306 		snprintf(buf, sizeof(buf), "%6.2fGB",
307 			(double)size / (1024 * 1024 * 1024LL));
308 	} else {
309 		snprintf(buf, sizeof(buf), "%6.2fTB",
310 			(double)size / (1024 * 1024 * 1024LL * 1024LL));
311 	}
312 	return(buf);
313 }
314 
315 /*
316  * Convert a string to a 64 bit signed integer with various requirements.
317  */
318 static int64_t
319 getsize(const char *str, int64_t minval, int64_t maxval, int powerof2)
320 {
321 	int64_t val;
322 	char *ptr;
323 
324 	val = strtoll(str, &ptr, 0);
325 	switch(*ptr) {
326 	case 't':
327 	case 'T':
328 		val *= 1024;
329 		/* fall through */
330 	case 'g':
331 	case 'G':
332 		val *= 1024;
333 		/* fall through */
334 	case 'm':
335 	case 'M':
336 		val *= 1024;
337 		/* fall through */
338 	case 'k':
339 	case 'K':
340 		val *= 1024;
341 		break;
342 	default:
343 		errx(1, "Unknown suffix in number '%s'\n", str);
344 		/* not reached */
345 	}
346 	if (ptr[1]) {
347 		errx(1, "Unknown suffix in number '%s'\n", str);
348 		/* not reached */
349 	}
350 	if (val < minval) {
351 		errx(1, "Value too small: %s, min is %s\n",
352 		     str, sizetostr(minval));
353 		/* not reached */
354 	}
355 	if (val > maxval) {
356 		errx(1, "Value too large: %s, max is %s\n",
357 		     str, sizetostr(maxval));
358 		/* not reached */
359 	}
360 	if ((powerof2 & 1) && (val ^ (val - 1)) != ((val << 1) - 1)) {
361 		errx(1, "Value not power of 2: %s\n", str);
362 		/* not reached */
363 	}
364 	if ((powerof2 & 2) && (val & HAMMER2_NEWFS_ALIGNMASK)) {
365 		errx(1, "Value not an integral multiple of %dK: %s",
366 		     HAMMER2_NEWFS_ALIGN / 1024, str);
367 		/* not reached */
368 	}
369 	return(val);
370 }
371 
372 static uint64_t
373 nowtime(void)
374 {
375 	struct timeval tv;
376 	uint64_t xtime;
377 
378 	gettimeofday(&tv, NULL);
379 	xtime = tv.tv_sec * 1000000LL + tv.tv_usec;
380 	return(xtime);
381 }
382 
383 /*
384  * Figure out how big the volume is.
385  */
386 static
387 hammer2_off_t
388 check_volume(const char *path, int *fdp)
389 {
390 	struct partinfo pinfo;
391 	struct stat st;
392 	hammer2_off_t size;
393 
394 	/*
395 	 * Get basic information about the volume
396 	 */
397 	*fdp = open(path, O_RDWR);
398 	if (*fdp < 0)
399 		err(1, "Unable to open %s R+W", path);
400 	if (ioctl(*fdp, DIOCGPART, &pinfo) < 0) {
401 		/*
402 		 * Allow the formatting of regular files as HAMMER2 volumes
403 		 */
404 		if (fstat(*fdp, &st) < 0)
405 			err(1, "Unable to stat %s", path);
406 		size = st.st_size;
407 	} else {
408 		/*
409 		 * When formatting a block device as a HAMMER2 volume the
410 		 * sector size must be compatible.  HAMMER2 uses 64K
411 		 * filesystem buffers but logical buffers for direct I/O
412 		 * can be as small as HAMMER2_LOGSIZE (16KB).
413 		 */
414 		if (pinfo.reserved_blocks) {
415 			errx(1, "HAMMER cannot be placed in a partition "
416 				"which overlaps the disklabel or MBR");
417 		}
418 		if (pinfo.media_blksize > HAMMER2_PBUFSIZE ||
419 		    HAMMER2_PBUFSIZE % pinfo.media_blksize) {
420 			errx(1, "A media sector size of %d is not supported",
421 			     pinfo.media_blksize);
422 		}
423 		size = pinfo.media_size;
424 	}
425 	printf("Volume %-15s size %s\n", path, sizetostr(size));
426 	return (size);
427 }
428 
429 /*
430  * Create the volume header, the super-root directory inode, and
431  * the writable snapshot subdirectory (named via the label) which
432  * is to be the initial mount point, or at least the first mount point.
433  *
434  * [----reserved_area----][boot_area][aux_area]
435  * [[vol_hdr]...         ]                      [sroot][root]
436  *
437  * The sroot and root inodes eat 512 bytes each.  newfs labels can only be
438  * 64 bytes so the root (snapshot) inode does not need to extend past 512
439  * bytes.  We use the correct hash slot correct but note that because
440  * directory hashes are chained 16x, any slot in the inode will work.
441  *
442  * Also format the allocation map.
443  *
444  * NOTE: The passed total_space is 8MB-aligned to avoid edge cases.
445  */
446 static
447 void
448 format_hammer2(int fd, hammer2_off_t total_space, hammer2_off_t free_space)
449 {
450 	char *buf = malloc(HAMMER2_PBUFSIZE);
451 	hammer2_volume_data_t *vol;
452 	hammer2_inode_data_t *rawip;
453 	hammer2_blockref_t sroot_blockref;
454 	hammer2_blockref_t root_blockref;
455 	uint64_t now;
456 	hammer2_off_t volu_base = 0;
457 	hammer2_off_t boot_base = HAMMER2_ZONE_SEG;
458 	hammer2_off_t aux_base = boot_base + BootAreaSize;
459 	hammer2_off_t alloc_base = aux_base + AuxAreaSize;
460 	hammer2_off_t tmp_base;
461 	size_t n;
462 	int i;
463 
464 	/*
465 	 * Clear the entire reserve for the first 2G segment and
466 	 * make sure we can write to the last block.
467 	 */
468 	bzero(buf, HAMMER2_PBUFSIZE);
469 	tmp_base = volu_base;
470 	for (i = 0; i < HAMMER2_ZONE_BLOCKS_SEG; ++i) {
471 		n = pwrite(fd, buf, HAMMER2_PBUFSIZE, tmp_base);
472 		if (n != HAMMER2_PBUFSIZE) {
473 			perror("write");
474 			exit(1);
475 		}
476 		tmp_base += HAMMER2_PBUFSIZE;
477 	}
478 
479 	n = pwrite(fd, buf, HAMMER2_PBUFSIZE,
480 		   volu_base + total_space - HAMMER2_PBUFSIZE);
481 	if (n != HAMMER2_PBUFSIZE) {
482 		perror("write (at-end-of-volume)");
483 		exit(1);
484 	}
485 
486 	/*
487 	 * Make sure alloc_base won't cross the reserved area at the
488 	 * beginning of each 2GB zone.
489 	 *
490 	 * Reserve space for the super-root inode and the root inode.
491 	 * Make sure they are in the same 64K block to simplify our code.
492 	 */
493 	assert((alloc_base & HAMMER2_PBUFMASK) == 0);
494 	assert(alloc_base < HAMMER2_ZONE_BYTES64 - HAMMER2_ZONE_SEG);
495 
496 	alloc_base &= ~HAMMER2_PBUFMASK64;
497 	alloc_direct(&alloc_base, &sroot_blockref, HAMMER2_INODE_BYTES);
498 	alloc_direct(&alloc_base, &root_blockref, HAMMER2_INODE_BYTES);
499 	assert(((sroot_blockref.data_off ^ root_blockref.data_off) &
500 		HAMMER2_OFF_MASK_HI) == 0);
501 
502 	bzero(buf, HAMMER2_PBUFSIZE);
503 	now = nowtime();
504 
505 	/*
506 	 * Format the root directory inode, which is left empty.
507 	 */
508 	rawip = (void *)(buf + (HAMMER2_OFF_MASK_LO & root_blockref.data_off));
509 	rawip->version = HAMMER2_INODE_VERSION_ONE;
510 	rawip->ctime = now;
511 	rawip->mtime = now;
512 	/* rawip->atime = now; NOT IMPL MUST BE ZERO */
513 	rawip->btime = now;
514 	rawip->type = HAMMER2_OBJTYPE_DIRECTORY;
515 	rawip->mode = 0755;
516 	rawip->inum = 1;		/* root inode, inumber 1 */
517 	rawip->nlinks = 1; 		/* directory link count compat */
518 
519 	rawip->name_len = strlen(Label);
520 	bcopy(Label, rawip->filename, rawip->name_len);
521 	rawip->name_key = dirhash(rawip->filename, rawip->name_len);
522 
523 	/*
524 	 * Compression mode and supported copyids.
525 	 *
526 	 * Do not allow compression when creating a "boot" label
527 	 * (pfs-create also does the same if the pfs is named "boot")
528 	 */
529 	if (strcmp(Label, "boot") == 0)
530 		rawip->comp_algo = HAMMER2_COMP_AUTOZERO;
531 	else
532 		rawip->comp_algo = HAMMER2_COMP_NEWFS_DEFAULT;
533 
534 	rawip->pfs_clid = Hammer2_RPFSId;
535 	rawip->pfs_type = HAMMER2_PFSTYPE_MASTER;
536 	rawip->op_flags |= HAMMER2_OPFLAG_PFSROOT;
537 
538 	/* rawip->u.blockset is left empty */
539 
540 	/*
541 	 * The root blockref will be stored in the super-root inode as
542 	 * the only directory entry.  The copyid here is the actual copyid
543 	 * of the storage ref.
544 	 *
545 	 * The key field for a directory entry's blockref is essentially
546 	 * the name key for the entry.
547 	 */
548 	root_blockref.key = rawip->name_key;
549 	root_blockref.copyid = HAMMER2_COPYID_LOCAL;
550 	root_blockref.keybits = 0;
551 	root_blockref.check.iscsi32.value =
552 			hammer2_icrc32(rawip, sizeof(*rawip));
553 	root_blockref.type = HAMMER2_BREF_TYPE_INODE;
554 	root_blockref.methods = HAMMER2_ENC_CHECK(HAMMER2_CHECK_ISCSI32) |
555 				HAMMER2_ENC_COMP(HAMMER2_COMP_NONE);
556 
557 	/*
558 	 * Format the super-root directory inode, giving it one directory
559 	 * entry (root_blockref) and fixup the icrc method.
560 	 *
561 	 * The superroot contains one directory entry pointing at the root
562 	 * inode (named via the label).  Inodes contain one blockset which
563 	 * is fully associative so we can put the entry anywhere without
564 	 * having to worry about the hash.  Use index 0.
565 	 */
566 	rawip = (void *)(buf + (HAMMER2_OFF_MASK_LO & sroot_blockref.data_off));
567 	rawip->version = HAMMER2_INODE_VERSION_ONE;
568 	rawip->ctime = now;
569 	rawip->mtime = now;
570 	/* rawip->atime = now; NOT IMPL MUST BE ZERO */
571 	rawip->btime = now;
572 	rawip->type = HAMMER2_OBJTYPE_DIRECTORY;
573 	rawip->mode = 0700;		/* super-root - root only */
574 	rawip->inum = 0;		/* super root inode, inumber 0 */
575 	rawip->nlinks = 2; 		/* directory link count compat */
576 
577 	rawip->name_len = 0;		/* super-root is unnamed */
578 	rawip->name_key = 0;
579 
580 	rawip->comp_algo = HAMMER2_COMP_AUTOZERO;
581 
582 	/*
583 	 * The super-root is flagged as a PFS and typically given its own
584 	 * random FSID, making it possible to mirror an entire HAMMER2 disk
585 	 * snapshots and all if desired.  PFS ids are used to match up
586 	 * mirror sources and targets and cluster copy sources and targets.
587 	 */
588 	rawip->pfs_clid = Hammer2_SPFSId;
589 	rawip->pfs_type = HAMMER2_PFSTYPE_MASTER;
590 	rawip->op_flags |= HAMMER2_OPFLAG_PFSROOT;
591 
592 	/*
593 	 * The super-root has one directory entry pointing at the named
594 	 * root inode.
595 	 */
596 	rawip->u.blockset.blockref[0] = root_blockref;
597 
598 	/*
599 	 * The sroot blockref will be stored in the volume header.
600 	 */
601 	sroot_blockref.copyid = HAMMER2_COPYID_LOCAL;
602 	sroot_blockref.keybits = 0;
603 	sroot_blockref.check.iscsi32.value =
604 					hammer2_icrc32(rawip, sizeof(*rawip));
605 	sroot_blockref.type = HAMMER2_BREF_TYPE_INODE;
606 	sroot_blockref.methods = HAMMER2_ENC_CHECK(HAMMER2_CHECK_ISCSI32) |
607 			         HAMMER2_ENC_COMP(HAMMER2_COMP_AUTOZERO);
608 	rawip = NULL;
609 
610 	/*
611 	 * Write out the 64K HAMMER2 block containing the root and sroot.
612 	 */
613 	n = pwrite(fd, buf, HAMMER2_PBUFSIZE,
614 		   root_blockref.data_off & HAMMER2_OFF_MASK_HI);
615 	if (n != HAMMER2_PBUFSIZE) {
616 		perror("write");
617 		exit(1);
618 	}
619 
620 	/*
621 	 * Format the volume header.
622 	 *
623 	 * The volume header points to sroot_blockref.  Also be absolutely
624 	 * sure that allocator_beg is set.
625 	 */
626 	bzero(buf, HAMMER2_PBUFSIZE);
627 	vol = (void *)buf;
628 
629 	vol->magic = HAMMER2_VOLUME_ID_HBO;
630 	vol->boot_beg = boot_base;
631 	vol->boot_end = boot_base + BootAreaSize;
632 	vol->aux_beg = aux_base;
633 	vol->aux_end = aux_base + AuxAreaSize;
634 	vol->volu_size = total_space;
635 	vol->version = Hammer2Version;
636 	vol->flags = 0;
637 
638 	vol->fsid = Hammer2_FSId;
639 	vol->fstype = Hammer2_FSType;
640 
641 	vol->peer_type = HAMMER2_PEER_HAMMER2;	/* LNK_CONN identification */
642 
643 	vol->allocator_size = free_space;
644 	vol->allocator_free = free_space;
645 	vol->allocator_beg = alloc_base;
646 
647 	vol->sroot_blockset.blockref[0] = sroot_blockref;
648 	vol->mirror_tid = 0;
649 	vol->alloc_tid = 16;
650 	vol->icrc_sects[HAMMER2_VOL_ICRC_SECT1] =
651 			hammer2_icrc32((char *)vol + HAMMER2_VOLUME_ICRC1_OFF,
652 				       HAMMER2_VOLUME_ICRC1_SIZE);
653 
654 	/*
655 	 * Set ICRC_SECT0 after all remaining elements of sect0 have been
656 	 * populated in the volume header.  Note hat ICRC_SECT* (except for
657 	 * SECT0) are part of sect0.
658 	 */
659 	vol->icrc_sects[HAMMER2_VOL_ICRC_SECT0] =
660 			hammer2_icrc32((char *)vol + HAMMER2_VOLUME_ICRC0_OFF,
661 				       HAMMER2_VOLUME_ICRC0_SIZE);
662 	vol->icrc_volheader =
663 			hammer2_icrc32((char *)vol + HAMMER2_VOLUME_ICRCVH_OFF,
664 				       HAMMER2_VOLUME_ICRCVH_SIZE);
665 
666 	/*
667 	 * Write the volume header and all alternates.
668 	 */
669 	for (i = 0; i < HAMMER2_NUM_VOLHDRS; ++i) {
670 		if (i * HAMMER2_ZONE_BYTES64 >= total_space)
671 			break;
672 		n = pwrite(fd, buf, HAMMER2_PBUFSIZE,
673 			   volu_base + i * HAMMER2_ZONE_BYTES64);
674 		if (n != HAMMER2_PBUFSIZE) {
675 			perror("write");
676 			exit(1);
677 		}
678 	}
679 
680 	/*
681 	 * Cleanup
682 	 */
683 	free(buf);
684 }
685 
686 static void
687 alloc_direct(hammer2_off_t *basep, hammer2_blockref_t *bref, size_t bytes)
688 {
689 	int radix;
690 
691 	radix = 0;
692 	assert(bytes);
693 	while ((bytes & 1) == 0) {
694 		bytes >>= 1;
695 		++radix;
696 	}
697 	assert(bytes == 1);
698 	if (radix < HAMMER2_MIN_RADIX)
699 		radix = HAMMER2_MIN_RADIX;
700 
701 	bzero(bref, sizeof(*bref));
702 	bref->data_off = *basep | radix;
703 	bref->vradix = radix;
704 
705 	*basep += 1U << radix;
706 }
707 
708 /*
709  * Borrow HAMMER1's directory hash algorithm #1 with a few modifications.
710  * The filename is split into fields which are hashed separately and then
711  * added together.
712  *
713  * Differences include: bit 63 must be set to 1 for HAMMER2 (HAMMER1 sets
714  * it to 0), this is because bit63=0 is used for hidden hardlinked inodes.
715  * (This means we do not need to do a 0-check/or-with-0x100000000 either).
716  *
717  * Also, the iscsi crc code is used instead of the old crc32 code.
718  */
719 static hammer2_key_t
720 dirhash(const unsigned char *name, size_t len)
721 {
722 	const unsigned char *aname = name;
723 	uint32_t crcx;
724 	uint64_t key;
725 	size_t i;
726 	size_t j;
727 
728 	/*
729 	 * Filesystem version 6 or better will create directories
730 	 * using the ALG1 dirhash.  This hash breaks the filename
731 	 * up into domains separated by special characters and
732 	 * hashes each domain independently.
733 	 *
734 	 * We also do a simple sub-sort using the first character
735 	 * of the filename in the top 5-bits.
736 	 */
737 	key = 0;
738 
739 	/*
740 	 * m32
741 	 */
742 	crcx = 0;
743 	for (i = j = 0; i < len; ++i) {
744 		if (aname[i] == '.' ||
745 		    aname[i] == '-' ||
746 		    aname[i] == '_' ||
747 		    aname[i] == '~') {
748 			if (i != j)
749 				crcx += hammer2_icrc32(aname + j, i - j);
750 			j = i + 1;
751 		}
752 	}
753 	if (i != j)
754 		crcx += hammer2_icrc32(aname + j, i - j);
755 
756 	/*
757 	 * The directory hash utilizes the top 32 bits of the 64-bit key.
758 	 * Bit 63 must be set to 1.
759 	 */
760 	crcx |= 0x80000000U;
761 	key |= (uint64_t)crcx << 32;
762 
763 	/*
764 	 * l16 - crc of entire filename
765 	 *
766 	 * This crc reduces degenerate hash collision conditions
767 	 */
768 	crcx = hammer2_icrc32(aname, len);
769 	crcx = crcx ^ (crcx << 16);
770 	key |= crcx & 0xFFFF0000U;
771 
772 	/*
773 	 * Set bit 15.  This allows readdir to strip bit 63 so a positive
774 	 * 64-bit cookie/offset can always be returned, and still guarantee
775 	 * that the values 0x0000-0x7FFF are available for artificial entries.
776 	 * ('.' and '..').
777 	 */
778 	key |= 0x8000U;
779 
780 	return (key);
781 }
782