aboutsummaryrefslogtreecommitdiff
path: root/include/fstree.h
blob: 9f47f76f36c4d5cca92d4fd1ab9f5dc58557096a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
/* SPDX-License-Identifier: GPL-3.0-or-later */
/*
 * fstree.h
 *
 * Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
 */
#ifndef FSTREE_H
#define FSTREE_H

#include "config.h"

#include <sys/types.h>
#include <sys/stat.h>
#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>
#include <stdio.h>

#include "str_table.h"

#define FSTREE_XATTR_KEY_BUCKETS 31
#define FSTREE_XATTR_VALUE_BUCKETS 511

typedef struct tree_node_t tree_node_t;
typedef struct file_info_t file_info_t;
typedef struct dir_info_t dir_info_t;
typedef struct fstree_t fstree_t;
typedef struct tree_xattr_t tree_xattr_t;

enum {
	FILE_FLAG_HAS_FRAGMENT = 0x01,

	FILE_FLAG_FRAGMENT_IS_DUPLICATE = 0x02,

	FILE_FLAG_BLOCKS_ARE_DUPLICATE = 0x04,
};

enum {
	DIR_SCAN_KEEP_TIME = 0x01,

	DIR_SCAN_ONE_FILESYSTEM = 0x02,
};

/* Encapsulates a set of key-value pairs attached to a tree_node_t */
struct tree_xattr_t {
	/* Number of key-value pairs */
	size_t num_attr;

	/* Total size of the array, i.e. it's capacity */
	size_t max_attr;

	/* Offset of the meta data block where the pairs are stored */
	uint64_t block;

	/* Offset into a meta data block where the pairs start */
	uint32_t offset;

	/* Number of bytes written to disk */
	uint32_t size;

	/* Incremental index within all xattr blocks */
	size_t index;

	/* Back reference to the tree node this was created for */
	tree_node_t *owner;

	/* linked list pointer of list of attributes in @ref fstree_t */
	tree_xattr_t *next;

	/* Array with pairs of key-value tupples */
	struct {
		uint32_t key_index;
		uint32_t value_index;
	} attr[];
};

/* Additional meta data stored in a tree_node_t for regular files. */
struct file_info_t {
	/* Linked list pointer for files in fstree_t */
	file_info_t *next;

	/* Path to the input file. */
	char *input_file;

	uint64_t size;

	/* Number of bytes not written to disk because they are 0 */
	uint64_t sparse;

	/* Absolute position of the first data block. */
	uint64_t startblock;

	/* If the size is not a multiple of the block size, this holds an
	   index into the fragment table. */
	uint32_t fragment;

	/* Byte offset into the fragment block. */
	uint32_t fragment_offset;

	uint32_t fragment_chksum;

	/* combination of FILE_FLAG_* flags */
	uint32_t flags;

	/* Stores data about each full data block. */
	struct {
		uint32_t chksum;

		/* Bit (1 << 24) is set if the block is stored uncompressed. */
		uint32_t size;
	} blocks[];
};

/* Additional meta data stored in a tree_node_t for directories */
struct dir_info_t {
	/* Linked list head for children in the directory */
	tree_node_t *children;

	/* Size on disk. Computed and updated on the fly while writing
	   directory meta data to disk. */
	uint64_t size;

	/* Start block offset, relative to directory table start. */
	uint64_t start_block;

	/* Byte offset into the uncompressed meta data block. */
	uint32_t block_offset;

	/* Set to true for implicitly generated directories.  */
	bool created_implicitly;
};

/* A node in a file system tree */
struct tree_node_t {
	/* Parent directory children linked list pointer. */
	tree_node_t *next;

	/* Root node has this set to NULL. */
	tree_node_t *parent;

	/* For the root node, this points to an empty string. */
	char *name;

	/*
	  A pointer to an extended attribute array or NULL if unused.

	  This field is not stored in-line and taken care of by the generic
	  fstree cleanup code, since it is generatde after the tree already
	  exists and shared across multiple nodes.
	*/
	tree_xattr_t *xattr;

	uint32_t uid;
	uint32_t gid;
	uint32_t inode_num;
	uint32_t mod_time;
	uint16_t mode;

	/* SquashFS inode refernce number. 32 bit offset of the meta data
	   block start (relative to inode table start), shifted left by 16
	   and ored with a 13 bit offset into the uncompressed meta data block.

	   Generated on the fly when writing inodes. */
	uint64_t inode_ref;

	/* Type specific data. Pointers are into payload area blow. */
	union {
		dir_info_t *dir;
		file_info_t *file;
		char *slink_target;
		uint64_t devno;
	} data;

	uint8_t payload[];
};

/* Encapsulates a file system tree */
struct fstree_t {
	struct stat defaults;
	size_t block_size;
	size_t inode_tbl_size;

	str_table_t xattr_keys;
	str_table_t xattr_values;

	tree_node_t *root;
	tree_xattr_t *xattr;

	/* linear array of tree nodes. inode number is array index */
	tree_node_t **inode_table;

	/* linear linked list of all regular files */
	file_info_t *files;
};

/*
  Initializing means copying over the default values and creating a root node.
  On error, an error message is written to stderr.

  `block_size` is the the data block size for regular files.

  The string `defaults` can specify default attributes (mode, uid, gid, mtime)
  as a comma seperated list of key value paris (<key>=<value>[,...]). The string
  is passed to getsubopt and will be altered.

  Returns 0 on success.
*/
int fstree_init(fstree_t *fs, size_t block_size, char *defaults);

void fstree_cleanup(fstree_t *fs);

/*
  Create a tree node from a struct stat, node name and extra data.

  For symlinks, the extra part is interpreted as target. For regular files, it
  is interpreted as input path (can be NULL). The name doesn't have to be null
  terminated, a length has to be specified.

  This function does not print anything to stderr, instead it sets an
  appropriate errno value.

  The resulting node can be freed with a single free() call.
*/
tree_node_t *fstree_mknode(fstree_t *fs, tree_node_t *parent, const char *name,
			   size_t name_len, const char *extra,
			   const struct stat *sb);

/*
  Add a node to an fstree at a specific path.

  If some components of the path don't exist, they are created as directories
  with default permissions, like mkdir -p would, and marked as implcitily
  created. A subsequent call that tries to create an existing tree node will
  fail, except if the target is an implicitly created directory node and the
  call tries to create it as a directory (this will simply overwrite the
  permissions and ownership). The implicitly created flag is then cleared.
  Subsequent attempts to create an existing directory again will then also
  fail.

  This function does not print anything to stderr, instead it sets an
  appropriate errno value. Internally it uses fstree_mknode to create the node.
*/
tree_node_t *fstree_add_generic(fstree_t *fs, const char *path,
				const struct stat *sb, const char *extra);

/*
  Add an extended attribute key value pair to a tree node.

  Returns 0 on success, prints error to stderr on failure.
*/
int fstree_add_xattr(fstree_t *fs, tree_node_t *node,
		     const char *key, const char *value);

/* Recompute running index number of all xattr blocks. */
void fstree_xattr_reindex(fstree_t *fs);

/* Sort and dedupliciate xattr blocks, then recumpute the index numbers. */
void fstree_xattr_deduplicate(fstree_t *fs);

/*
  Parses the file format accepted by gensquashfs and produce a file system
  tree from it. File input paths are interpreted as relative to the current
  working directory.

  Data is read from the given file pointer. The filename is only used for
  producing error messages.

  On failure, an error report with filename and line number is written
  to stderr.

  Returns 0 on success.
 */
int fstree_from_file(fstree_t *fs, const char *filename, FILE *fp);

/*
  Recursively scan a directory and generate a file system tree from it.

  Returns 0 on success, prints errors to stderr.
 */
int fstree_from_dir(fstree_t *fs, const char *path, unsigned int flags);

/* Add labels from an SELinux labeling file to all tree nodes.
   Returns 0 on success. Internally prints errors to stderr. */
int fstree_relabel_selinux(fstree_t *fs, const char *filename);

/* Returns 0 on success. Prints to stderr on failure */
int fstree_gen_inode_table(fstree_t *fs);

void fstree_gen_file_list(fstree_t *fs);

/*
  Generate a string holding the full path of a node. Returned
  string must be freed.

  Returns NULL on failure and sets errno.
*/
char *fstree_get_path(tree_node_t *node);

/* get a struct stat from a tree node */
void fstree_node_stat(fstree_t *fs, tree_node_t *node, struct stat *sb);

/* ASCIIbetically sort a linked list of tree nodes */
tree_node_t *tree_node_list_sort(tree_node_t *head);

/* ASCIIbetically sort all sub directories recursively */
void tree_node_sort_recursive(tree_node_t *root);

/* resolve a path to a tree node. Returns NULL on failure and sets errno */
tree_node_t *fstree_node_from_path(fstree_t *fs, const char *path);

/*
  Walk through 'list' to find a file with a fragment that has
  the same size ('frag_size') and checksum ('chksum') as 'fi'.
  Processing stopps if 'fi' itself is found in the list.

  Returns NULL if no such fragment could be found.
*/
file_info_t *fragment_by_chksum(file_info_t *fi, uint32_t chksum,
				size_t frag_size, file_info_t *list,
				size_t block_size);

/*
  Walk through 'list' to find a file that contains the same sequence of blocks
  as 'file', comparing size and checksum. Processing stops if 'file' is found
  in the list.

  Returns NULL if no such fragment could be found.
 */
uint64_t find_equal_blocks(file_info_t *file, file_info_t *list,
			   size_t block_size);

/*
  Optimize the order of the fstree file list for unpacking as to avoid
  unpacking fragment blocks more than once and to improve locality when
  fetching data from disk. The resulting list is returned in 'out'.
  If num_jobs is > 1, the list is split up for parallel processing.
 */
void optimize_unpack_order(fstree_t *fs, size_t num_jobs,
			   file_info_t *out[num_jobs]);

#endif /* FSTREE_H */