1 /*-
2  * Copyright (c) 2008 Joerg Sonnenberger
3  * Copyright (c) 2009-2012 Michihiro NAKAJIMA
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18  * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26 
27 #include "archive_platform.h"
28 __FBSDID("$FreeBSD: head/lib/libarchive/archive_write_set_format_mtree.c 201171 2009-12-29 06:39:07Z kientzle $");
29 
30 #ifdef HAVE_SYS_TYPES_H
31 #include <sys/types.h>
32 #endif
33 #include <errno.h>
34 #include <stdlib.h>
35 #include <string.h>
36 
37 #include "archive.h"
38 #include "archive_digest_private.h"
39 #include "archive_entry.h"
40 #include "archive_private.h"
41 #include "archive_rb.h"
42 #include "archive_string.h"
43 #include "archive_write_private.h"
44 
45 #define INDENTNAMELEN	15
46 #define MAXLINELEN	80
47 #define SET_KEYS	\
48 	(F_FLAGS | F_GID | F_GNAME | F_MODE | F_TYPE | F_UID | F_UNAME)
49 
50 struct attr_counter {
51 	struct attr_counter *prev;
52 	struct attr_counter *next;
53 	struct mtree_entry *m_entry;
54 	int count;
55 };
56 
57 struct att_counter_set {
58 	struct attr_counter *uid_list;
59 	struct attr_counter *gid_list;
60 	struct attr_counter *mode_list;
61 	struct attr_counter *flags_list;
62 };
63 
64 struct mtree_chain {
65 	struct mtree_entry *first;
66 	struct mtree_entry **last;
67 };
68 
69 /*
70  * The Data only for a directory file.
71  */
72 struct dir_info {
73 	struct archive_rb_tree rbtree;
74 	struct mtree_chain children;
75 	struct mtree_entry *chnext;
76 	int virtual;
77 };
78 
79 /*
80  * The Data only for a regular file.
81  */
82 struct reg_info {
83 	int compute_sum;
84 	uint32_t crc;
85 #ifdef ARCHIVE_HAS_MD5
86 	unsigned char buf_md5[16];
87 #endif
88 #ifdef ARCHIVE_HAS_RMD160
89 	unsigned char buf_rmd160[20];
90 #endif
91 #ifdef ARCHIVE_HAS_SHA1
92 	unsigned char buf_sha1[20];
93 #endif
94 #ifdef ARCHIVE_HAS_SHA256
95 	unsigned char buf_sha256[32];
96 #endif
97 #ifdef ARCHIVE_HAS_SHA384
98 	unsigned char buf_sha384[48];
99 #endif
100 #ifdef ARCHIVE_HAS_SHA512
101 	unsigned char buf_sha512[64];
102 #endif
103 };
104 
105 struct mtree_entry {
106 	struct archive_rb_node rbnode;
107 	struct mtree_entry *next;
108 	struct mtree_entry *parent;
109 	struct dir_info *dir_info;
110 	struct reg_info *reg_info;
111 
112 	struct archive_string parentdir;
113 	struct archive_string basename;
114 	struct archive_string pathname;
115 	struct archive_string symlink;
116 	struct archive_string uname;
117 	struct archive_string gname;
118 	struct archive_string fflags_text;
119 	unsigned int nlink;
120 	mode_t filetype;
121 	mode_t mode;
122 	int64_t size;
123 	int64_t uid;
124 	int64_t gid;
125 	time_t mtime;
126 	long mtime_nsec;
127 	unsigned long fflags_set;
128 	unsigned long fflags_clear;
129 	dev_t rdevmajor;
130 	dev_t rdevminor;
131 	dev_t devmajor;
132 	dev_t devminor;
133 	int64_t ino;
134 };
135 
136 struct mtree_writer {
137 	struct mtree_entry *mtree_entry;
138 	struct mtree_entry *root;
139 	struct mtree_entry *cur_dirent;
140 	struct archive_string cur_dirstr;
141 	struct mtree_chain file_list;
142 
143 	struct archive_string ebuf;
144 	struct archive_string buf;
145 	int first;
146 	uint64_t entry_bytes_remaining;
147 
148 	/*
149 	 * Set global value.
150 	 */
151 	struct {
152 		int		processing;
153 		mode_t		type;
154 		int		keys;
155 		int64_t		uid;
156 		int64_t		gid;
157 		mode_t		mode;
158 		unsigned long	fflags_set;
159 		unsigned long	fflags_clear;
160 	} set;
161 	struct att_counter_set	acs;
162 	int classic;
163 	int depth;
164 
165 	/* check sum */
166 	int compute_sum;
167 	uint32_t crc;
168 	uint64_t crc_len;
169 #ifdef ARCHIVE_HAS_MD5
170 	archive_md5_ctx md5ctx;
171 #endif
172 #ifdef ARCHIVE_HAS_RMD160
173 	archive_rmd160_ctx rmd160ctx;
174 #endif
175 #ifdef ARCHIVE_HAS_SHA1
176 	archive_sha1_ctx sha1ctx;
177 #endif
178 #ifdef ARCHIVE_HAS_SHA256
179 	archive_sha256_ctx sha256ctx;
180 #endif
181 #ifdef ARCHIVE_HAS_SHA384
182 	archive_sha384_ctx sha384ctx;
183 #endif
184 #ifdef ARCHIVE_HAS_SHA512
185 	archive_sha512_ctx sha512ctx;
186 #endif
187 	/* Keyword options */
188 	int keys;
189 #define	F_CKSUM		0x00000001		/* check sum */
190 #define	F_DEV		0x00000002		/* device type */
191 #define	F_DONE		0x00000004		/* directory done */
192 #define	F_FLAGS		0x00000008		/* file flags */
193 #define	F_GID		0x00000010		/* gid */
194 #define	F_GNAME		0x00000020		/* group name */
195 #define	F_IGN		0x00000040		/* ignore */
196 #define	F_MAGIC		0x00000080		/* name has magic chars */
197 #define	F_MD5		0x00000100		/* MD5 digest */
198 #define	F_MODE		0x00000200		/* mode */
199 #define	F_NLINK		0x00000400		/* number of links */
200 #define	F_NOCHANGE 	0x00000800		/* If owner/mode "wrong", do
201 						 * not change */
202 #define	F_OPT		0x00001000		/* existence optional */
203 #define	F_RMD160 	0x00002000		/* RIPEMD160 digest */
204 #define	F_SHA1		0x00004000		/* SHA-1 digest */
205 #define	F_SIZE		0x00008000		/* size */
206 #define	F_SLINK		0x00010000		/* symbolic link */
207 #define	F_TAGS		0x00020000		/* tags */
208 #define	F_TIME		0x00040000		/* modification time */
209 #define	F_TYPE		0x00080000		/* file type */
210 #define	F_UID		0x00100000		/* uid */
211 #define	F_UNAME		0x00200000		/* user name */
212 #define	F_VISIT		0x00400000		/* file visited */
213 #define	F_SHA256	0x00800000		/* SHA-256 digest */
214 #define	F_SHA384	0x01000000		/* SHA-384 digest */
215 #define	F_SHA512	0x02000000		/* SHA-512 digest */
216 #define	F_INO		0x04000000		/* inode number */
217 #define	F_RESDEV	0x08000000		/* device ID on which the
218 						 * entry resides */
219 
220 	/* Options */
221 	int dironly;		/* If it is set, ignore all files except
222 				 * directory files, like mtree(8) -d option. */
223 	int indent;		/* If it is set, indent output data. */
224 	int output_global_set;	/* If it is set, use /set keyword to set
225 				 * global values. When generating mtree
226 				 * classic format, it is set by default. */
227 };
228 
229 #define DEFAULT_KEYS	(F_DEV | F_FLAGS | F_GID | F_GNAME | F_SLINK | F_MODE\
230 			 | F_NLINK | F_SIZE | F_TIME | F_TYPE | F_UID\
231 			 | F_UNAME)
232 #define attr_counter_set_reset	attr_counter_set_free
233 
234 static void attr_counter_free(struct attr_counter **);
235 static int attr_counter_inc(struct attr_counter **, struct attr_counter *,
236 	struct attr_counter *, struct mtree_entry *);
237 static struct attr_counter * attr_counter_new(struct mtree_entry *,
238 	struct attr_counter *);
239 static int attr_counter_set_collect(struct mtree_writer *,
240 	struct mtree_entry *);
241 static void attr_counter_set_free(struct mtree_writer *);
242 static int get_global_set_keys(struct mtree_writer *, struct mtree_entry *);
243 static int mtree_entry_add_child_tail(struct mtree_entry *,
244 	struct mtree_entry *);
245 static int mtree_entry_create_virtual_dir(struct archive_write *, const char *,
246 	struct mtree_entry **);
247 static int mtree_entry_cmp_node(const struct archive_rb_node *,
248 	const struct archive_rb_node *);
249 static int mtree_entry_cmp_key(const struct archive_rb_node *, const void *);
250 static int mtree_entry_exchange_same_entry(struct archive_write *,
251     struct mtree_entry *, struct mtree_entry *);
252 static void mtree_entry_free(struct mtree_entry *);
253 static int mtree_entry_new(struct archive_write *, struct archive_entry *,
254 	struct mtree_entry **);
255 static void mtree_entry_register_free(struct mtree_writer *);
256 static void mtree_entry_register_init(struct mtree_writer *);
257 static int mtree_entry_setup_filenames(struct archive_write *,
258 	struct mtree_entry *, struct archive_entry *);
259 static int mtree_entry_tree_add(struct archive_write *, struct mtree_entry **);
260 static void sum_init(struct mtree_writer *);
261 static void sum_update(struct mtree_writer *, const void *, size_t);
262 static void sum_final(struct mtree_writer *, struct reg_info *);
263 static void sum_write(struct archive_string *, struct reg_info *);
264 static int write_mtree_entry(struct archive_write *, struct mtree_entry *);
265 static int write_dot_dot_entry(struct archive_write *, struct mtree_entry *);
266 
267 #define	COMPUTE_CRC(var, ch)	(var) = (var) << 8 ^ crctab[(var) >> 24 ^ (ch)]
268 static const uint32_t crctab[] = {
269 	0x0,
270 	0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b,
271 	0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6,
272 	0x2b4bcb61, 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
273 	0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9, 0x5f15adac,
274 	0x5bd4b01b, 0x569796c2, 0x52568b75, 0x6a1936c8, 0x6ed82b7f,
275 	0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3, 0x709f7b7a,
276 	0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
277 	0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58,
278 	0xbaea46ef, 0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033,
279 	0xa4ad16ea, 0xa06c0b5d, 0xd4326d90, 0xd0f37027, 0xddb056fe,
280 	0xd9714b49, 0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
281 	0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1, 0xe13ef6f4,
282 	0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0,
283 	0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5,
284 	0x2ac12072, 0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
285 	0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca, 0x7897ab07,
286 	0x7c56b6b0, 0x71159069, 0x75d48dde, 0x6b93dddb, 0x6f52c06c,
287 	0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1,
288 	0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
289 	0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b,
290 	0xbb60adfc, 0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698,
291 	0x832f1041, 0x87ee0df6, 0x99a95df3, 0x9d684044, 0x902b669d,
292 	0x94ea7b2a, 0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
293 	0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2, 0xc6bcf05f,
294 	0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34,
295 	0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80,
296 	0x644fc637, 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
297 	0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f, 0x5c007b8a,
298 	0x58c1663d, 0x558240e4, 0x51435d53, 0x251d3b9e, 0x21dc2629,
299 	0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5, 0x3f9b762c,
300 	0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
301 	0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e,
302 	0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65,
303 	0xeba91bbc, 0xef68060b, 0xd727bbb6, 0xd3e6a601, 0xdea580d8,
304 	0xda649d6f, 0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
305 	0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7, 0xae3afba2,
306 	0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71,
307 	0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74,
308 	0x857130c3, 0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
309 	0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c, 0x7b827d21,
310 	0x7f436096, 0x7200464f, 0x76c15bf8, 0x68860bfd, 0x6c47164a,
311 	0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e, 0x18197087,
312 	0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
313 	0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d,
314 	0x2056cd3a, 0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce,
315 	0xcc2b1d17, 0xc8ea00a0, 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb,
316 	0xdbee767c, 0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
317 	0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4, 0x89b8fd09,
318 	0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662,
319 	0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf,
320 	0xa2f33668, 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
321 };
322 
323 static const unsigned char safe_char[256] = {
324 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 00 - 0F */
325 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 10 - 1F */
326 	/* !"$%&'()*+,-./  EXCLUSION:0x20( ) 0x23(#) */
327 	0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 20 - 2F */
328 	/* 0123456789:;<>?  EXCLUSION:0x3d(=) */
329 	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, /* 30 - 3F */
330 	/* @ABCDEFGHIJKLMNO */
331 	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 40 - 4F */
332 	/* PQRSTUVWXYZ[]^_ EXCLUSION:0x5c(\)  */
333 	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, /* 50 - 5F */
334 	/* `abcdefghijklmno */
335 	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 60 - 6F */
336 	/* pqrstuvwxyz{|}~ */
337 	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, /* 70 - 7F */
338 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 80 - 8F */
339 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 90 - 9F */
340 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* A0 - AF */
341 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* B0 - BF */
342 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* C0 - CF */
343 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* D0 - DF */
344 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* E0 - EF */
345 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* F0 - FF */
346 };
347 
348 static void
mtree_quote(struct archive_string * s,const char * str)349 mtree_quote(struct archive_string *s, const char *str)
350 {
351 	const char *start;
352 	char buf[4];
353 	unsigned char c;
354 
355 	for (start = str; *str != '\0'; ++str) {
356 		if (safe_char[*(const unsigned char *)str])
357 			continue;
358 		if (start != str)
359 			archive_strncat(s, start, str - start);
360 		c = (unsigned char)*str;
361 		buf[0] = '\\';
362 		buf[1] = (c / 64) + '0';
363 		buf[2] = (c / 8 % 8) + '0';
364 		buf[3] = (c % 8) + '0';
365 		archive_strncat(s, buf, 4);
366 		start = str + 1;
367 	}
368 
369 	if (start != str)
370 		archive_strncat(s, start, str - start);
371 }
372 
373 /*
374  * Indent a line as mtree utility to be readable for people.
375  */
376 static void
mtree_indent(struct mtree_writer * mtree)377 mtree_indent(struct mtree_writer *mtree)
378 {
379 	int i, fn, nd, pd;
380 	const char *r, *s, *x;
381 
382 	if (mtree->classic) {
383 		if (mtree->indent) {
384 			nd = 0;
385 			pd = mtree->depth * 4;
386 		} else {
387 			nd = mtree->depth?4:0;
388 			pd = 0;
389 		}
390 	} else
391 		nd = pd = 0;
392 	fn = 1;
393 	s = r = mtree->ebuf.s;
394 	x = NULL;
395 	while (*r == ' ')
396 		r++;
397 	while ((r = strchr(r, ' ')) != NULL) {
398 		if (fn) {
399 			fn = 0;
400 			for (i = 0; i < nd + pd; i++)
401 				archive_strappend_char(&mtree->buf, ' ');
402 			archive_strncat(&mtree->buf, s, r - s);
403 			if (nd + (r -s) > INDENTNAMELEN) {
404 				archive_strncat(&mtree->buf, " \\\n", 3);
405 				for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
406 					archive_strappend_char(&mtree->buf, ' ');
407 			} else {
408 				for (i = (int)(r -s + nd);
409 				    i < (INDENTNAMELEN + 1); i++)
410 					archive_strappend_char(&mtree->buf, ' ');
411 			}
412 			s = ++r;
413 			x = NULL;
414 			continue;
415 		}
416 		if (pd + (r - s) <= MAXLINELEN - 3 - INDENTNAMELEN)
417 			x = r++;
418 		else {
419 			if (x == NULL)
420 				x = r;
421 			archive_strncat(&mtree->buf, s, x - s);
422 			archive_strncat(&mtree->buf, " \\\n", 3);
423 			for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
424 				archive_strappend_char(&mtree->buf, ' ');
425 			s = r = ++x;
426 			x = NULL;
427 		}
428 	}
429 	if (fn) {
430 		for (i = 0; i < nd + pd; i++)
431 			archive_strappend_char(&mtree->buf, ' ');
432 		archive_strcat(&mtree->buf, s);
433 		s += strlen(s);
434 	}
435 	if (x != NULL && pd + strlen(s) > MAXLINELEN - 3 - INDENTNAMELEN) {
436 		/* Last keyword is longer. */
437 		archive_strncat(&mtree->buf, s, x - s);
438 		archive_strncat(&mtree->buf, " \\\n", 3);
439 		for (i = 0; i < (INDENTNAMELEN + 1 + pd); i++)
440 			archive_strappend_char(&mtree->buf, ' ');
441 		s = ++x;
442 	}
443 	archive_strcat(&mtree->buf, s);
444 	archive_string_empty(&mtree->ebuf);
445 }
446 
447 /*
448  * Write /set keyword.
449  * Set most used value of uid,gid,mode and fflags, which are
450  * collected by attr_counter_set_collect() function.
451  */
452 static void
write_global(struct mtree_writer * mtree)453 write_global(struct mtree_writer *mtree)
454 {
455 	struct archive_string setstr;
456 	struct archive_string unsetstr;
457 	struct att_counter_set *acs;
458 	int keys, oldkeys, effkeys;
459 
460 	archive_string_init(&setstr);
461 	archive_string_init(&unsetstr);
462 	keys = mtree->keys & SET_KEYS;
463 	oldkeys = mtree->set.keys;
464 	effkeys = keys;
465 	acs = &mtree->acs;
466 	if (mtree->set.processing) {
467 		/*
468 		 * Check if the global data needs updating.
469 		 */
470 		effkeys &= ~F_TYPE;
471 		if (acs->uid_list == NULL)
472 			effkeys &= ~(F_UNAME | F_UID);
473 		else if (oldkeys & (F_UNAME | F_UID)) {
474 			if (acs->uid_list->count < 2 ||
475 			    mtree->set.uid == acs->uid_list->m_entry->uid)
476 				effkeys &= ~(F_UNAME | F_UID);
477 		}
478 		if (acs->gid_list == NULL)
479 			effkeys &= ~(F_GNAME | F_GID);
480 		else if (oldkeys & (F_GNAME | F_GID)) {
481 			if (acs->gid_list->count < 2 ||
482 			    mtree->set.gid == acs->gid_list->m_entry->gid)
483 				effkeys &= ~(F_GNAME | F_GID);
484 		}
485 		if (acs->mode_list == NULL)
486 			effkeys &= ~F_MODE;
487 		else if (oldkeys & F_MODE) {
488 			if (acs->mode_list->count < 2 ||
489 			    mtree->set.mode == acs->mode_list->m_entry->mode)
490 				effkeys &= ~F_MODE;
491 		}
492 		if (acs->flags_list == NULL)
493 			effkeys &= ~F_FLAGS;
494 		else if ((oldkeys & F_FLAGS) != 0) {
495 			if (acs->flags_list->count < 2 ||
496 			    (acs->flags_list->m_entry->fflags_set ==
497 				mtree->set.fflags_set &&
498 			     acs->flags_list->m_entry->fflags_clear ==
499 				mtree->set.fflags_clear))
500 				effkeys &= ~F_FLAGS;
501 		}
502 	} else {
503 		if (acs->uid_list == NULL)
504 			keys &= ~(F_UNAME | F_UID);
505 		if (acs->gid_list == NULL)
506 			keys &= ~(F_GNAME | F_GID);
507 		if (acs->mode_list == NULL)
508 			keys &= ~F_MODE;
509 		if (acs->flags_list == NULL)
510 			keys &= ~F_FLAGS;
511 	}
512 	if ((keys & effkeys & F_TYPE) != 0) {
513 		if (mtree->dironly) {
514 			archive_strcat(&setstr, " type=dir");
515 			mtree->set.type = AE_IFDIR;
516 		} else {
517 			archive_strcat(&setstr, " type=file");
518 			mtree->set.type = AE_IFREG;
519 		}
520 	}
521 	if ((keys & effkeys & F_UNAME) != 0) {
522 		if (archive_strlen(&(acs->uid_list->m_entry->uname)) > 0) {
523 			archive_strcat(&setstr, " uname=");
524 			mtree_quote(&setstr, acs->uid_list->m_entry->uname.s);
525 		} else {
526 			keys &= ~F_UNAME;
527 			if ((oldkeys & F_UNAME) != 0)
528 				archive_strcat(&unsetstr, " uname");
529 		}
530 	}
531 	if ((keys & effkeys & F_UID) != 0) {
532 		mtree->set.uid = acs->uid_list->m_entry->uid;
533 		archive_string_sprintf(&setstr, " uid=%jd",
534 		    (intmax_t)mtree->set.uid);
535 	}
536 	if ((keys & effkeys & F_GNAME) != 0) {
537 		if (archive_strlen(&(acs->gid_list->m_entry->gname)) > 0) {
538 			archive_strcat(&setstr, " gname=");
539 			mtree_quote(&setstr, acs->gid_list->m_entry->gname.s);
540 		} else {
541 			keys &= ~F_GNAME;
542 			if ((oldkeys & F_GNAME) != 0)
543 				archive_strcat(&unsetstr, " gname");
544 		}
545 	}
546 	if ((keys & effkeys & F_GID) != 0) {
547 		mtree->set.gid = acs->gid_list->m_entry->gid;
548 		archive_string_sprintf(&setstr, " gid=%jd",
549 		    (intmax_t)mtree->set.gid);
550 	}
551 	if ((keys & effkeys & F_MODE) != 0) {
552 		mtree->set.mode = acs->mode_list->m_entry->mode;
553 		archive_string_sprintf(&setstr, " mode=%o",
554 		    (unsigned int)mtree->set.mode);
555 	}
556 	if ((keys & effkeys & F_FLAGS) != 0) {
557 		if (archive_strlen(
558 		    &(acs->flags_list->m_entry->fflags_text)) > 0) {
559 			archive_strcat(&setstr, " flags=");
560 			mtree_quote(&setstr,
561 			    acs->flags_list->m_entry->fflags_text.s);
562 			mtree->set.fflags_set =
563 			    acs->flags_list->m_entry->fflags_set;
564 			mtree->set.fflags_clear =
565 			    acs->flags_list->m_entry->fflags_clear;
566 		} else {
567 			keys &= ~F_FLAGS;
568 			if ((oldkeys & F_FLAGS) != 0)
569 				archive_strcat(&unsetstr, " flags");
570 		}
571 	}
572 	if (unsetstr.length > 0)
573 		archive_string_sprintf(&mtree->buf, "/unset%s\n", unsetstr.s);
574 	archive_string_free(&unsetstr);
575 	if (setstr.length > 0)
576 		archive_string_sprintf(&mtree->buf, "/set%s\n", setstr.s);
577 	archive_string_free(&setstr);
578 	mtree->set.keys = keys;
579 	mtree->set.processing = 1;
580 }
581 
582 static struct attr_counter *
attr_counter_new(struct mtree_entry * me,struct attr_counter * prev)583 attr_counter_new(struct mtree_entry *me, struct attr_counter *prev)
584 {
585 	struct attr_counter *ac;
586 
587 	ac = malloc(sizeof(*ac));
588 	if (ac != NULL) {
589 		ac->prev = prev;
590 		ac->next = NULL;
591 		ac->count = 1;
592 		ac->m_entry = me;
593 	}
594 	return (ac);
595 }
596 
597 static void
attr_counter_free(struct attr_counter ** top)598 attr_counter_free(struct attr_counter **top)
599 {
600 	struct attr_counter *ac, *tac;
601 
602 	if (*top == NULL)
603 		return;
604 	ac = *top;
605         while (ac != NULL) {
606 		tac = ac->next;
607 		free(ac);
608 		ac = tac;
609 	}
610 	*top = NULL;
611 }
612 
613 static int
attr_counter_inc(struct attr_counter ** top,struct attr_counter * ac,struct attr_counter * last,struct mtree_entry * me)614 attr_counter_inc(struct attr_counter **top, struct attr_counter *ac,
615     struct attr_counter *last, struct mtree_entry *me)
616 {
617 	struct attr_counter *pac;
618 
619 	if (ac != NULL) {
620 		ac->count++;
621 		if (*top == ac || ac->prev->count >= ac->count)
622 			return (0);
623 		for (pac = ac->prev; pac; pac = pac->prev) {
624 			if (pac->count >= ac->count)
625 				break;
626 		}
627 		ac->prev->next = ac->next;
628 		if (ac->next != NULL)
629 			ac->next->prev = ac->prev;
630 		if (pac != NULL) {
631 			ac->prev = pac;
632 			ac->next = pac->next;
633 			pac->next = ac;
634 			if (ac->next != NULL)
635 				ac->next->prev = ac;
636 		} else {
637 			ac->prev = NULL;
638 			ac->next = *top;
639 			*top = ac;
640 			ac->next->prev = ac;
641 		}
642 	} else if (last != NULL) {
643 		ac = attr_counter_new(me, last);
644 		if (ac == NULL)
645 			return (-1);
646 		last->next = ac;
647 	}
648 	return (0);
649 }
650 
651 /*
652  * Tabulate uid,gid,mode and fflags of a entry in order to be used for /set.
653  */
654 static int
attr_counter_set_collect(struct mtree_writer * mtree,struct mtree_entry * me)655 attr_counter_set_collect(struct mtree_writer *mtree, struct mtree_entry *me)
656 {
657 	struct attr_counter *ac, *last;
658 	struct att_counter_set *acs = &mtree->acs;
659 	int keys = mtree->keys;
660 
661 	if (keys & (F_UNAME | F_UID)) {
662 		if (acs->uid_list == NULL) {
663 			acs->uid_list = attr_counter_new(me, NULL);
664 			if (acs->uid_list == NULL)
665 				return (-1);
666 		} else {
667 			last = NULL;
668 			for (ac = acs->uid_list; ac; ac = ac->next) {
669 				if (ac->m_entry->uid == me->uid)
670 					break;
671 				last = ac;
672 			}
673 			if (attr_counter_inc(&acs->uid_list, ac, last, me) < 0)
674 				return (-1);
675 		}
676 	}
677 	if (keys & (F_GNAME | F_GID)) {
678 		if (acs->gid_list == NULL) {
679 			acs->gid_list = attr_counter_new(me, NULL);
680 			if (acs->gid_list == NULL)
681 				return (-1);
682 		} else {
683 			last = NULL;
684 			for (ac = acs->gid_list; ac; ac = ac->next) {
685 				if (ac->m_entry->gid == me->gid)
686 					break;
687 				last = ac;
688 			}
689 			if (attr_counter_inc(&acs->gid_list, ac, last, me) < 0)
690 				return (-1);
691 		}
692 	}
693 	if (keys & F_MODE) {
694 		if (acs->mode_list == NULL) {
695 			acs->mode_list = attr_counter_new(me, NULL);
696 			if (acs->mode_list == NULL)
697 				return (-1);
698 		} else {
699 			last = NULL;
700 			for (ac = acs->mode_list; ac; ac = ac->next) {
701 				if (ac->m_entry->mode == me->mode)
702 					break;
703 				last = ac;
704 			}
705 			if (attr_counter_inc(&acs->mode_list, ac, last, me) < 0)
706 				return (-1);
707 		}
708 	}
709 	if (keys & F_FLAGS) {
710 		if (acs->flags_list == NULL) {
711 			acs->flags_list = attr_counter_new(me, NULL);
712 			if (acs->flags_list == NULL)
713 				return (-1);
714 		} else {
715 			last = NULL;
716 			for (ac = acs->flags_list; ac; ac = ac->next) {
717 				if (ac->m_entry->fflags_set == me->fflags_set &&
718 				    ac->m_entry->fflags_clear ==
719 							me->fflags_clear)
720 					break;
721 				last = ac;
722 			}
723 			if (attr_counter_inc(&acs->flags_list, ac, last, me) < 0)
724 				return (-1);
725 		}
726 	}
727 
728 	return (0);
729 }
730 
731 static void
attr_counter_set_free(struct mtree_writer * mtree)732 attr_counter_set_free(struct mtree_writer *mtree)
733 {
734 	struct att_counter_set *acs = &mtree->acs;
735 
736 	attr_counter_free(&acs->uid_list);
737 	attr_counter_free(&acs->gid_list);
738 	attr_counter_free(&acs->mode_list);
739 	attr_counter_free(&acs->flags_list);
740 }
741 
742 static int
get_global_set_keys(struct mtree_writer * mtree,struct mtree_entry * me)743 get_global_set_keys(struct mtree_writer *mtree, struct mtree_entry *me)
744 {
745 	int keys;
746 
747 	keys = mtree->keys;
748 
749 	/*
750 	 * If a keyword has been set by /set, we do not need to
751 	 * output it.
752 	 */
753 	if (mtree->set.keys == 0)
754 		return (keys);/* /set is not used. */
755 
756 	if ((mtree->set.keys & (F_GNAME | F_GID)) != 0 &&
757 	     mtree->set.gid == me->gid)
758 		keys &= ~(F_GNAME | F_GID);
759 	if ((mtree->set.keys & (F_UNAME | F_UID)) != 0 &&
760 	     mtree->set.uid == me->uid)
761 		keys &= ~(F_UNAME | F_UID);
762 	if (mtree->set.keys & F_FLAGS) {
763 		if (mtree->set.fflags_set == me->fflags_set &&
764 		    mtree->set.fflags_clear == me->fflags_clear)
765 			keys &= ~F_FLAGS;
766 	}
767 	if ((mtree->set.keys & F_MODE) != 0 && mtree->set.mode == me->mode)
768 		keys &= ~F_MODE;
769 
770 	switch (me->filetype) {
771 	case AE_IFLNK: case AE_IFSOCK: case AE_IFCHR:
772 	case AE_IFBLK: case AE_IFIFO:
773 		break;
774 	case AE_IFDIR:
775 		if ((mtree->set.keys & F_TYPE) != 0 &&
776 		    mtree->set.type == AE_IFDIR)
777 			keys &= ~F_TYPE;
778 		break;
779 	case AE_IFREG:
780 	default:	/* Handle unknown file types as regular files. */
781 		if ((mtree->set.keys & F_TYPE) != 0 &&
782 		    mtree->set.type == AE_IFREG)
783 			keys &= ~F_TYPE;
784 		break;
785 	}
786 
787 	return (keys);
788 }
789 
790 static int
mtree_entry_new(struct archive_write * a,struct archive_entry * entry,struct mtree_entry ** m_entry)791 mtree_entry_new(struct archive_write *a, struct archive_entry *entry,
792     struct mtree_entry **m_entry)
793 {
794 	struct mtree_entry *me;
795 	const char *s;
796 	int r;
797 	static const struct archive_rb_tree_ops rb_ops = {
798 		mtree_entry_cmp_node, mtree_entry_cmp_key
799 	};
800 
801 	me = calloc(1, sizeof(*me));
802 	if (me == NULL) {
803 		archive_set_error(&a->archive, ENOMEM,
804 		    "Can't allocate memory for a mtree entry");
805 		*m_entry = NULL;
806 		return (ARCHIVE_FATAL);
807 	}
808 
809 	r = mtree_entry_setup_filenames(a, me, entry);
810 	if (r < ARCHIVE_WARN) {
811 		mtree_entry_free(me);
812 		*m_entry = NULL;
813 		return (r);
814 	}
815 
816 	if ((s = archive_entry_symlink(entry)) != NULL)
817 		archive_strcpy(&me->symlink, s);
818 	me->nlink = archive_entry_nlink(entry);
819 	me->filetype = archive_entry_filetype(entry);
820 	me->mode = archive_entry_mode(entry) & 07777;
821 	me->uid = archive_entry_uid(entry);
822 	me->gid = archive_entry_gid(entry);
823 	if ((s = archive_entry_uname(entry)) != NULL)
824 		archive_strcpy(&me->uname, s);
825 	if ((s = archive_entry_gname(entry)) != NULL)
826 		archive_strcpy(&me->gname, s);
827 	if ((s = archive_entry_fflags_text(entry)) != NULL)
828 		archive_strcpy(&me->fflags_text, s);
829 	archive_entry_fflags(entry, &me->fflags_set, &me->fflags_clear);
830 	me->mtime = archive_entry_mtime(entry);
831 	me->mtime_nsec = archive_entry_mtime_nsec(entry);
832 	me->rdevmajor = archive_entry_rdevmajor(entry);
833 	me->rdevminor = archive_entry_rdevminor(entry);
834 	me->devmajor = archive_entry_devmajor(entry);
835 	me->devminor = archive_entry_devminor(entry);
836 	me->ino = archive_entry_ino(entry);
837 	me->size = archive_entry_size(entry);
838 	if (me->filetype == AE_IFDIR) {
839 		me->dir_info = calloc(1, sizeof(*me->dir_info));
840 		if (me->dir_info == NULL) {
841 			mtree_entry_free(me);
842 			archive_set_error(&a->archive, ENOMEM,
843 			    "Can't allocate memory for a mtree entry");
844 			*m_entry = NULL;
845 			return (ARCHIVE_FATAL);
846 		}
847 		__archive_rb_tree_init(&me->dir_info->rbtree, &rb_ops);
848 		me->dir_info->children.first = NULL;
849 		me->dir_info->children.last = &(me->dir_info->children.first);
850 		me->dir_info->chnext = NULL;
851 	} else if (me->filetype == AE_IFREG) {
852 		me->reg_info = calloc(1, sizeof(*me->reg_info));
853 		if (me->reg_info == NULL) {
854 			mtree_entry_free(me);
855 			archive_set_error(&a->archive, ENOMEM,
856 			    "Can't allocate memory for a mtree entry");
857 			*m_entry = NULL;
858 			return (ARCHIVE_FATAL);
859 		}
860 		me->reg_info->compute_sum = 0;
861 	}
862 
863 	*m_entry = me;
864 	return (ARCHIVE_OK);
865 }
866 
867 static void
mtree_entry_free(struct mtree_entry * me)868 mtree_entry_free(struct mtree_entry *me)
869 {
870 	archive_string_free(&me->parentdir);
871 	archive_string_free(&me->basename);
872 	archive_string_free(&me->pathname);
873 	archive_string_free(&me->symlink);
874 	archive_string_free(&me->uname);
875 	archive_string_free(&me->gname);
876 	archive_string_free(&me->fflags_text);
877 	free(me->dir_info);
878 	free(me->reg_info);
879 	free(me);
880 }
881 
882 static int
archive_write_mtree_header(struct archive_write * a,struct archive_entry * entry)883 archive_write_mtree_header(struct archive_write *a,
884     struct archive_entry *entry)
885 {
886 	struct mtree_writer *mtree= a->format_data;
887 	struct mtree_entry *mtree_entry;
888 	int r, r2;
889 
890 	if (mtree->first) {
891 		mtree->first = 0;
892 		archive_strcat(&mtree->buf, "#mtree\n");
893 		if ((mtree->keys & SET_KEYS) == 0)
894 			mtree->output_global_set = 0;/* Disabled. */
895 	}
896 
897 	mtree->entry_bytes_remaining = archive_entry_size(entry);
898 
899 	/* While directory only mode, we do not handle non directory files. */
900 	if (mtree->dironly && archive_entry_filetype(entry) != AE_IFDIR)
901 		return (ARCHIVE_OK);
902 
903 	r2 = mtree_entry_new(a, entry, &mtree_entry);
904 	if (r2 < ARCHIVE_WARN)
905 		return (r2);
906 	r = mtree_entry_tree_add(a, &mtree_entry);
907 	if (r < ARCHIVE_WARN) {
908 		mtree_entry_free(mtree_entry);
909 		return (r);
910 	}
911 	mtree->mtree_entry = mtree_entry;
912 
913 	/* If the current file is a regular file, we have to
914 	 * compute the sum of its content.
915 	 * Initialize a bunch of sum check context. */
916 	if (mtree_entry->reg_info)
917 		sum_init(mtree);
918 
919 	return (r2);
920 }
921 
922 static int
write_mtree_entry(struct archive_write * a,struct mtree_entry * me)923 write_mtree_entry(struct archive_write *a, struct mtree_entry *me)
924 {
925 	struct mtree_writer *mtree = a->format_data;
926 	struct archive_string *str;
927 	int keys, ret;
928 
929 	if (me->dir_info) {
930 		if (mtree->classic) {
931 			/*
932 			 * Output a comment line to describe the full
933 			 * pathname of the entry as mtree utility does
934 			 * while generating classic format.
935 			 */
936 			if (!mtree->dironly)
937 				archive_strappend_char(&mtree->buf, '\n');
938 			if (me->parentdir.s)
939 				archive_string_sprintf(&mtree->buf,
940 				    "# %s/%s\n",
941 				    me->parentdir.s, me->basename.s);
942 			else
943 				archive_string_sprintf(&mtree->buf,
944 				    "# %s\n",
945 				    me->basename.s);
946 		}
947 		if (mtree->output_global_set)
948 			write_global(mtree);
949 	}
950 	archive_string_empty(&mtree->ebuf);
951 	str = (mtree->indent || mtree->classic)? &mtree->ebuf : &mtree->buf;
952 
953 	if (!mtree->classic && me->parentdir.s) {
954 		/*
955 		 * If generating format is not classic one(v1), output
956 		 * a full pathname.
957 		 */
958 		mtree_quote(str, me->parentdir.s);
959 		archive_strappend_char(str, '/');
960 	}
961 	mtree_quote(str, me->basename.s);
962 
963 	keys = get_global_set_keys(mtree, me);
964 	if ((keys & F_NLINK) != 0 &&
965 	    me->nlink != 1 && me->filetype != AE_IFDIR)
966 		archive_string_sprintf(str, " nlink=%u", me->nlink);
967 
968 	if ((keys & F_GNAME) != 0 && archive_strlen(&me->gname) > 0) {
969 		archive_strcat(str, " gname=");
970 		mtree_quote(str, me->gname.s);
971 	}
972 	if ((keys & F_UNAME) != 0 && archive_strlen(&me->uname) > 0) {
973 		archive_strcat(str, " uname=");
974 		mtree_quote(str, me->uname.s);
975 	}
976 	if ((keys & F_FLAGS) != 0) {
977 		if (archive_strlen(&me->fflags_text) > 0) {
978 			archive_strcat(str, " flags=");
979 			mtree_quote(str, me->fflags_text.s);
980 		} else if (mtree->set.processing &&
981 		    (mtree->set.keys & F_FLAGS) != 0)
982 			/* Overwrite the global parameter. */
983 			archive_strcat(str, " flags=none");
984 	}
985 	if ((keys & F_TIME) != 0)
986 		archive_string_sprintf(str, " time=%jd.%jd",
987 		    (intmax_t)me->mtime, (intmax_t)me->mtime_nsec);
988 	if ((keys & F_MODE) != 0)
989 		archive_string_sprintf(str, " mode=%o", (unsigned int)me->mode);
990 	if ((keys & F_GID) != 0)
991 		archive_string_sprintf(str, " gid=%jd", (intmax_t)me->gid);
992 	if ((keys & F_UID) != 0)
993 		archive_string_sprintf(str, " uid=%jd", (intmax_t)me->uid);
994 
995 	if ((keys & F_INO) != 0)
996 		archive_string_sprintf(str, " inode=%jd", (intmax_t)me->ino);
997 	if ((keys & F_RESDEV) != 0) {
998 		archive_string_sprintf(str,
999 		    " resdevice=native,%ju,%ju",
1000 		    (uintmax_t)me->devmajor,
1001 		    (uintmax_t)me->devminor);
1002 	}
1003 
1004 	switch (me->filetype) {
1005 	case AE_IFLNK:
1006 		if ((keys & F_TYPE) != 0)
1007 			archive_strcat(str, " type=link");
1008 		if ((keys & F_SLINK) != 0) {
1009 			archive_strcat(str, " link=");
1010 			mtree_quote(str, me->symlink.s);
1011 		}
1012 		break;
1013 	case AE_IFSOCK:
1014 		if ((keys & F_TYPE) != 0)
1015 			archive_strcat(str, " type=socket");
1016 		break;
1017 	case AE_IFCHR:
1018 		if ((keys & F_TYPE) != 0)
1019 			archive_strcat(str, " type=char");
1020 		if ((keys & F_DEV) != 0) {
1021 			archive_string_sprintf(str,
1022 			    " device=native,%ju,%ju",
1023 			    (uintmax_t)me->rdevmajor,
1024 			    (uintmax_t)me->rdevminor);
1025 		}
1026 		break;
1027 	case AE_IFBLK:
1028 		if ((keys & F_TYPE) != 0)
1029 			archive_strcat(str, " type=block");
1030 		if ((keys & F_DEV) != 0) {
1031 			archive_string_sprintf(str,
1032 			    " device=native,%ju,%ju",
1033 			    (uintmax_t)me->rdevmajor,
1034 			    (uintmax_t)me->rdevminor);
1035 		}
1036 		break;
1037 	case AE_IFDIR:
1038 		if ((keys & F_TYPE) != 0)
1039 			archive_strcat(str, " type=dir");
1040 		break;
1041 	case AE_IFIFO:
1042 		if ((keys & F_TYPE) != 0)
1043 			archive_strcat(str, " type=fifo");
1044 		break;
1045 	case AE_IFREG:
1046 	default:	/* Handle unknown file types as regular files. */
1047 		if ((keys & F_TYPE) != 0)
1048 			archive_strcat(str, " type=file");
1049 		if ((keys & F_SIZE) != 0)
1050 			archive_string_sprintf(str, " size=%jd",
1051 			    (intmax_t)me->size);
1052 		break;
1053 	}
1054 
1055 	/* Write a bunch of sum. */
1056 	if (me->reg_info)
1057 		sum_write(str, me->reg_info);
1058 
1059 	archive_strappend_char(str, '\n');
1060 	if (mtree->indent || mtree->classic)
1061 		mtree_indent(mtree);
1062 
1063 	if (mtree->buf.length > 32768) {
1064 		ret = __archive_write_output(
1065 			a, mtree->buf.s, mtree->buf.length);
1066 		archive_string_empty(&mtree->buf);
1067 	} else
1068 		ret = ARCHIVE_OK;
1069 	return (ret);
1070 }
1071 
1072 static int
write_dot_dot_entry(struct archive_write * a,struct mtree_entry * n)1073 write_dot_dot_entry(struct archive_write *a, struct mtree_entry *n)
1074 {
1075 	struct mtree_writer *mtree = a->format_data;
1076 	int ret;
1077 
1078 	if (n->parentdir.s) {
1079 		if (mtree->indent) {
1080 			int i, pd = mtree->depth * 4;
1081 			for (i = 0; i < pd; i++)
1082 				archive_strappend_char(&mtree->buf, ' ');
1083 		}
1084 		archive_string_sprintf(&mtree->buf, "# %s/%s\n",
1085 			n->parentdir.s, n->basename.s);
1086 	}
1087 
1088 	if (mtree->indent) {
1089 		archive_string_empty(&mtree->ebuf);
1090 		archive_strncat(&mtree->ebuf, "..\n\n", (mtree->dironly)?3:4);
1091 		mtree_indent(mtree);
1092 	} else
1093 		archive_strncat(&mtree->buf, "..\n\n", (mtree->dironly)?3:4);
1094 
1095 	if (mtree->buf.length > 32768) {
1096 		ret = __archive_write_output(
1097 			a, mtree->buf.s, mtree->buf.length);
1098 		archive_string_empty(&mtree->buf);
1099 	} else
1100 		ret = ARCHIVE_OK;
1101 	return (ret);
1102 }
1103 
1104 /*
1105  * Write mtree entries saved at attr_counter_set_collect() function.
1106  */
1107 static int
write_mtree_entry_tree(struct archive_write * a)1108 write_mtree_entry_tree(struct archive_write *a)
1109 {
1110 	struct mtree_writer *mtree = a->format_data;
1111 	struct mtree_entry *np = mtree->root;
1112 	struct archive_rb_node *n;
1113 	int ret;
1114 
1115 	do {
1116 		if (mtree->output_global_set) {
1117 			/*
1118 			 * Collect attribute information to know which value
1119 			 * is frequently used among the children.
1120 			 */
1121 			attr_counter_set_reset(mtree);
1122 			ARCHIVE_RB_TREE_FOREACH(n, &(np->dir_info->rbtree)) {
1123 				struct mtree_entry *e = (struct mtree_entry *)n;
1124 				if (attr_counter_set_collect(mtree, e) < 0) {
1125 					archive_set_error(&a->archive, ENOMEM,
1126 					    "Can't allocate memory");
1127 					return (ARCHIVE_FATAL);
1128 				}
1129 			}
1130 		}
1131 		if (!np->dir_info->virtual || mtree->classic) {
1132 			ret = write_mtree_entry(a, np);
1133 			if (ret != ARCHIVE_OK)
1134 				return (ARCHIVE_FATAL);
1135 		} else {
1136 			/* Whenever output_global_set is enabled
1137 			 * output global value(/set keywords)
1138 			 * even if the directory entry is not allowed
1139 			 * to be written because the global values
1140 			 * can be used for the children. */
1141 			if (mtree->output_global_set)
1142 				write_global(mtree);
1143 		}
1144 		/*
1145 		 * Output the attribute of all files except directory files.
1146 		 */
1147 		mtree->depth++;
1148 		ARCHIVE_RB_TREE_FOREACH(n, &(np->dir_info->rbtree)) {
1149 			struct mtree_entry *e = (struct mtree_entry *)n;
1150 
1151 			if (e->dir_info)
1152 				mtree_entry_add_child_tail(np, e);
1153 			else {
1154 				ret = write_mtree_entry(a, e);
1155 				if (ret != ARCHIVE_OK)
1156 					return (ARCHIVE_FATAL);
1157 			}
1158 		}
1159 		mtree->depth--;
1160 
1161 		if (np->dir_info->children.first != NULL) {
1162 			/*
1163 			 * Descend the tree.
1164 			 */
1165 			np = np->dir_info->children.first;
1166 			if (mtree->indent)
1167 				mtree->depth++;
1168 			continue;
1169 		} else if (mtree->classic) {
1170 			/*
1171 			 * While printing mtree classic, if there are not
1172 			 * any directory files(except "." and "..") in the
1173 			 * directory, output two dots ".." as returning
1174 			 * the parent directory.
1175 			 */
1176 			ret = write_dot_dot_entry(a, np);
1177 			if (ret != ARCHIVE_OK)
1178 				return (ARCHIVE_FATAL);
1179 		}
1180 
1181 		while (np != np->parent) {
1182 			if (np->dir_info->chnext == NULL) {
1183 				/*
1184 				 * Ascend the tree; go back to the parent.
1185 				 */
1186 				if (mtree->indent)
1187 					mtree->depth--;
1188 				if (mtree->classic) {
1189 					ret = write_dot_dot_entry(a,
1190 						np->parent);
1191 					if (ret != ARCHIVE_OK)
1192 						return (ARCHIVE_FATAL);
1193 				}
1194 				np = np->parent;
1195 			} else {
1196 				/*
1197 				 * Switch to next mtree entry in the directory.
1198 				 */
1199 				np = np->dir_info->chnext;
1200 				break;
1201 			}
1202 		}
1203 	} while (np != np->parent);
1204 
1205 	return (ARCHIVE_OK);
1206 }
1207 
1208 static int
archive_write_mtree_finish_entry(struct archive_write * a)1209 archive_write_mtree_finish_entry(struct archive_write *a)
1210 {
1211 	struct mtree_writer *mtree = a->format_data;
1212 	struct mtree_entry *me;
1213 
1214 	if ((me = mtree->mtree_entry) == NULL)
1215 		return (ARCHIVE_OK);
1216 	mtree->mtree_entry = NULL;
1217 
1218 	if (me->reg_info)
1219 		sum_final(mtree, me->reg_info);
1220 
1221 	return (ARCHIVE_OK);
1222 }
1223 
1224 static int
archive_write_mtree_close(struct archive_write * a)1225 archive_write_mtree_close(struct archive_write *a)
1226 {
1227 	struct mtree_writer *mtree= a->format_data;
1228 	int ret;
1229 
1230 	if (mtree->root != NULL) {
1231 		ret = write_mtree_entry_tree(a);
1232 		if (ret != ARCHIVE_OK)
1233 			return (ARCHIVE_FATAL);
1234 	}
1235 
1236 	archive_write_set_bytes_in_last_block(&a->archive, 1);
1237 
1238 	return __archive_write_output(a, mtree->buf.s, mtree->buf.length);
1239 }
1240 
1241 static ssize_t
archive_write_mtree_data(struct archive_write * a,const void * buff,size_t n)1242 archive_write_mtree_data(struct archive_write *a, const void *buff, size_t n)
1243 {
1244 	struct mtree_writer *mtree= a->format_data;
1245 
1246 	if (n > mtree->entry_bytes_remaining)
1247 		n = (size_t)mtree->entry_bytes_remaining;
1248 	mtree->entry_bytes_remaining -= n;
1249 
1250 	/* We don't need to compute a regular file sum */
1251 	if (mtree->mtree_entry == NULL)
1252 		return (n);
1253 
1254 	if (mtree->mtree_entry->filetype == AE_IFREG)
1255 		sum_update(mtree, buff, n);
1256 
1257 	return (n);
1258 }
1259 
1260 static int
archive_write_mtree_free(struct archive_write * a)1261 archive_write_mtree_free(struct archive_write *a)
1262 {
1263 	struct mtree_writer *mtree= a->format_data;
1264 
1265 	if (mtree == NULL)
1266 		return (ARCHIVE_OK);
1267 
1268 	/* Make sure we dot not leave any entries. */
1269 	mtree_entry_register_free(mtree);
1270 	archive_string_free(&mtree->cur_dirstr);
1271 	archive_string_free(&mtree->ebuf);
1272 	archive_string_free(&mtree->buf);
1273 	attr_counter_set_free(mtree);
1274 	free(mtree);
1275 	a->format_data = NULL;
1276 	return (ARCHIVE_OK);
1277 }
1278 
1279 static int
archive_write_mtree_options(struct archive_write * a,const char * key,const char * value)1280 archive_write_mtree_options(struct archive_write *a, const char *key,
1281     const char *value)
1282 {
1283 	struct mtree_writer *mtree= a->format_data;
1284 	int keybit = 0;
1285 
1286 	switch (key[0]) {
1287 	case 'a':
1288 		if (strcmp(key, "all") == 0)
1289 			keybit = ~0;
1290 		break;
1291 	case 'c':
1292 		if (strcmp(key, "cksum") == 0)
1293 			keybit = F_CKSUM;
1294 		break;
1295 	case 'd':
1296 		if (strcmp(key, "device") == 0)
1297 			keybit = F_DEV;
1298 		else if (strcmp(key, "dironly") == 0) {
1299 			mtree->dironly = (value != NULL)? 1: 0;
1300 			return (ARCHIVE_OK);
1301 		}
1302 		break;
1303 	case 'f':
1304 		if (strcmp(key, "flags") == 0)
1305 			keybit = F_FLAGS;
1306 		break;
1307 	case 'g':
1308 		if (strcmp(key, "gid") == 0)
1309 			keybit = F_GID;
1310 		else if (strcmp(key, "gname") == 0)
1311 			keybit = F_GNAME;
1312 		break;
1313 	case 'i':
1314 		if (strcmp(key, "indent") == 0) {
1315 			mtree->indent = (value != NULL)? 1: 0;
1316 			return (ARCHIVE_OK);
1317 		} else if (strcmp(key, "inode") == 0) {
1318 			keybit = F_INO;
1319 		}
1320 		break;
1321 	case 'l':
1322 		if (strcmp(key, "link") == 0)
1323 			keybit = F_SLINK;
1324 		break;
1325 	case 'm':
1326 		if (strcmp(key, "md5") == 0 ||
1327 		    strcmp(key, "md5digest") == 0)
1328 			keybit = F_MD5;
1329 		if (strcmp(key, "mode") == 0)
1330 			keybit = F_MODE;
1331 		break;
1332 	case 'n':
1333 		if (strcmp(key, "nlink") == 0)
1334 			keybit = F_NLINK;
1335 		break;
1336 	case 'r':
1337 		if (strcmp(key, "resdevice") == 0) {
1338 			keybit = F_RESDEV;
1339 		} else if (strcmp(key, "ripemd160digest") == 0 ||
1340 		    strcmp(key, "rmd160") == 0 ||
1341 		    strcmp(key, "rmd160digest") == 0)
1342 			keybit = F_RMD160;
1343 		break;
1344 	case 's':
1345 		if (strcmp(key, "sha1") == 0 ||
1346 		    strcmp(key, "sha1digest") == 0)
1347 			keybit = F_SHA1;
1348 		if (strcmp(key, "sha256") == 0 ||
1349 		    strcmp(key, "sha256digest") == 0)
1350 			keybit = F_SHA256;
1351 		if (strcmp(key, "sha384") == 0 ||
1352 		    strcmp(key, "sha384digest") == 0)
1353 			keybit = F_SHA384;
1354 		if (strcmp(key, "sha512") == 0 ||
1355 		    strcmp(key, "sha512digest") == 0)
1356 			keybit = F_SHA512;
1357 		if (strcmp(key, "size") == 0)
1358 			keybit = F_SIZE;
1359 		break;
1360 	case 't':
1361 		if (strcmp(key, "time") == 0)
1362 			keybit = F_TIME;
1363 		else if (strcmp(key, "type") == 0)
1364 			keybit = F_TYPE;
1365 		break;
1366 	case 'u':
1367 		if (strcmp(key, "uid") == 0)
1368 			keybit = F_UID;
1369 		else if (strcmp(key, "uname") == 0)
1370 			keybit = F_UNAME;
1371 		else if (strcmp(key, "use-set") == 0) {
1372 			mtree->output_global_set = (value != NULL)? 1: 0;
1373 			return (ARCHIVE_OK);
1374 		}
1375 		break;
1376 	}
1377 	if (keybit != 0) {
1378 		if (value != NULL)
1379 			mtree->keys |= keybit;
1380 		else
1381 			mtree->keys &= ~keybit;
1382 		return (ARCHIVE_OK);
1383 	}
1384 
1385 	/* Note: The "warn" return is just to inform the options
1386 	 * supervisor that we didn't handle it.  It will generate
1387 	 * a suitable error if no one used this option. */
1388 	return (ARCHIVE_WARN);
1389 }
1390 
1391 static int
archive_write_set_format_mtree_default(struct archive * _a,const char * fn)1392 archive_write_set_format_mtree_default(struct archive *_a, const char *fn)
1393 {
1394 	struct archive_write *a = (struct archive_write *)_a;
1395 	struct mtree_writer *mtree;
1396 
1397 	archive_check_magic(_a, ARCHIVE_WRITE_MAGIC, ARCHIVE_STATE_NEW, fn);
1398 
1399 	if (a->format_free != NULL)
1400 		(a->format_free)(a);
1401 
1402 	if ((mtree = calloc(1, sizeof(*mtree))) == NULL) {
1403 		archive_set_error(&a->archive, ENOMEM,
1404 		    "Can't allocate mtree data");
1405 		return (ARCHIVE_FATAL);
1406 	}
1407 
1408 	mtree->mtree_entry = NULL;
1409 	mtree->first = 1;
1410 	memset(&(mtree->set), 0, sizeof(mtree->set));
1411 	mtree->keys = DEFAULT_KEYS;
1412 	mtree->dironly = 0;
1413 	mtree->indent = 0;
1414 	archive_string_init(&mtree->ebuf);
1415 	archive_string_init(&mtree->buf);
1416 	mtree_entry_register_init(mtree);
1417 	a->format_data = mtree;
1418 	a->format_free = archive_write_mtree_free;
1419 	a->format_name = "mtree";
1420 	a->format_options = archive_write_mtree_options;
1421 	a->format_write_header = archive_write_mtree_header;
1422 	a->format_close = archive_write_mtree_close;
1423 	a->format_write_data = archive_write_mtree_data;
1424 	a->format_finish_entry = archive_write_mtree_finish_entry;
1425 	a->archive.archive_format = ARCHIVE_FORMAT_MTREE;
1426 	a->archive.archive_format_name = "mtree";
1427 
1428 	return (ARCHIVE_OK);
1429 }
1430 
1431 int
archive_write_set_format_mtree(struct archive * _a)1432 archive_write_set_format_mtree(struct archive *_a)
1433 {
1434 	return archive_write_set_format_mtree_default(_a,
1435 		"archive_write_set_format_mtree");
1436 }
1437 
1438 int
archive_write_set_format_mtree_classic(struct archive * _a)1439 archive_write_set_format_mtree_classic(struct archive *_a)
1440 {
1441 	int r;
1442 
1443 	r = archive_write_set_format_mtree_default(_a,
1444 		"archive_write_set_format_mtree_classic");
1445 	if (r == ARCHIVE_OK) {
1446 		struct archive_write *a = (struct archive_write *)_a;
1447 		struct mtree_writer *mtree;
1448 
1449 		mtree = (struct mtree_writer *)a->format_data;
1450 
1451 		/* Set to output a mtree archive in classic format. */
1452 		mtree->classic = 1;
1453 		/* Basically, mtree classic format uses '/set' global
1454 		 * value. */
1455 		mtree->output_global_set = 1;
1456 	}
1457 	return (r);
1458 }
1459 
1460 static void
sum_init(struct mtree_writer * mtree)1461 sum_init(struct mtree_writer *mtree)
1462 {
1463 
1464 	mtree->compute_sum = 0;
1465 
1466 	if (mtree->keys & F_CKSUM) {
1467 		mtree->compute_sum |= F_CKSUM;
1468 		mtree->crc = 0;
1469 		mtree->crc_len = 0;
1470 	}
1471 #ifdef ARCHIVE_HAS_MD5
1472 	if (mtree->keys & F_MD5) {
1473 		if (archive_md5_init(&mtree->md5ctx) == ARCHIVE_OK)
1474 			mtree->compute_sum |= F_MD5;
1475 		else
1476 			mtree->keys &= ~F_MD5;/* Not supported. */
1477 	}
1478 #endif
1479 #ifdef ARCHIVE_HAS_RMD160
1480 	if (mtree->keys & F_RMD160) {
1481 		if (archive_rmd160_init(&mtree->rmd160ctx) == ARCHIVE_OK)
1482 			mtree->compute_sum |= F_RMD160;
1483 		else
1484 			mtree->keys &= ~F_RMD160;/* Not supported. */
1485 	}
1486 #endif
1487 #ifdef ARCHIVE_HAS_SHA1
1488 	if (mtree->keys & F_SHA1) {
1489 		if (archive_sha1_init(&mtree->sha1ctx) == ARCHIVE_OK)
1490 			mtree->compute_sum |= F_SHA1;
1491 		else
1492 			mtree->keys &= ~F_SHA1;/* Not supported. */
1493 	}
1494 #endif
1495 #ifdef ARCHIVE_HAS_SHA256
1496 	if (mtree->keys & F_SHA256) {
1497 		if (archive_sha256_init(&mtree->sha256ctx) == ARCHIVE_OK)
1498 			mtree->compute_sum |= F_SHA256;
1499 		else
1500 			mtree->keys &= ~F_SHA256;/* Not supported. */
1501 	}
1502 #endif
1503 #ifdef ARCHIVE_HAS_SHA384
1504 	if (mtree->keys & F_SHA384) {
1505 		if (archive_sha384_init(&mtree->sha384ctx) == ARCHIVE_OK)
1506 			mtree->compute_sum |= F_SHA384;
1507 		else
1508 			mtree->keys &= ~F_SHA384;/* Not supported. */
1509 	}
1510 #endif
1511 #ifdef ARCHIVE_HAS_SHA512
1512 	if (mtree->keys & F_SHA512) {
1513 		if (archive_sha512_init(&mtree->sha512ctx) == ARCHIVE_OK)
1514 			mtree->compute_sum |= F_SHA512;
1515 		else
1516 			mtree->keys &= ~F_SHA512;/* Not supported. */
1517 	}
1518 #endif
1519 }
1520 
1521 static void
sum_update(struct mtree_writer * mtree,const void * buff,size_t n)1522 sum_update(struct mtree_writer *mtree, const void *buff, size_t n)
1523 {
1524 	if (mtree->compute_sum & F_CKSUM) {
1525 		/*
1526 		 * Compute a POSIX 1003.2 checksum
1527 		 */
1528 		const unsigned char *p;
1529 		size_t nn;
1530 
1531 		for (nn = n, p = buff; nn--; ++p)
1532 			COMPUTE_CRC(mtree->crc, *p);
1533 		mtree->crc_len += n;
1534 	}
1535 #ifdef ARCHIVE_HAS_MD5
1536 	if (mtree->compute_sum & F_MD5)
1537 		archive_md5_update(&mtree->md5ctx, buff, n);
1538 #endif
1539 #ifdef ARCHIVE_HAS_RMD160
1540 	if (mtree->compute_sum & F_RMD160)
1541 		archive_rmd160_update(&mtree->rmd160ctx, buff, n);
1542 #endif
1543 #ifdef ARCHIVE_HAS_SHA1
1544 	if (mtree->compute_sum & F_SHA1)
1545 		archive_sha1_update(&mtree->sha1ctx, buff, n);
1546 #endif
1547 #ifdef ARCHIVE_HAS_SHA256
1548 	if (mtree->compute_sum & F_SHA256)
1549 		archive_sha256_update(&mtree->sha256ctx, buff, n);
1550 #endif
1551 #ifdef ARCHIVE_HAS_SHA384
1552 	if (mtree->compute_sum & F_SHA384)
1553 		archive_sha384_update(&mtree->sha384ctx, buff, n);
1554 #endif
1555 #ifdef ARCHIVE_HAS_SHA512
1556 	if (mtree->compute_sum & F_SHA512)
1557 		archive_sha512_update(&mtree->sha512ctx, buff, n);
1558 #endif
1559 }
1560 
1561 static void
sum_final(struct mtree_writer * mtree,struct reg_info * reg)1562 sum_final(struct mtree_writer *mtree, struct reg_info *reg)
1563 {
1564 
1565 	if (mtree->compute_sum & F_CKSUM) {
1566 		uint64_t len;
1567 		/* Include the length of the file. */
1568 		for (len = mtree->crc_len; len != 0; len >>= 8)
1569 			COMPUTE_CRC(mtree->crc, len & 0xff);
1570 		reg->crc = ~mtree->crc;
1571 	}
1572 #ifdef ARCHIVE_HAS_MD5
1573 	if (mtree->compute_sum & F_MD5)
1574 		archive_md5_final(&mtree->md5ctx, reg->buf_md5);
1575 #endif
1576 #ifdef ARCHIVE_HAS_RMD160
1577 	if (mtree->compute_sum & F_RMD160)
1578 		archive_rmd160_final(&mtree->rmd160ctx, reg->buf_rmd160);
1579 #endif
1580 #ifdef ARCHIVE_HAS_SHA1
1581 	if (mtree->compute_sum & F_SHA1)
1582 		archive_sha1_final(&mtree->sha1ctx, reg->buf_sha1);
1583 #endif
1584 #ifdef ARCHIVE_HAS_SHA256
1585 	if (mtree->compute_sum & F_SHA256)
1586 		archive_sha256_final(&mtree->sha256ctx, reg->buf_sha256);
1587 #endif
1588 #ifdef ARCHIVE_HAS_SHA384
1589 	if (mtree->compute_sum & F_SHA384)
1590 		archive_sha384_final(&mtree->sha384ctx, reg->buf_sha384);
1591 #endif
1592 #ifdef ARCHIVE_HAS_SHA512
1593 	if (mtree->compute_sum & F_SHA512)
1594 		archive_sha512_final(&mtree->sha512ctx, reg->buf_sha512);
1595 #endif
1596 	/* Save what types of sum are computed. */
1597 	reg->compute_sum = mtree->compute_sum;
1598 }
1599 
1600 #if defined(ARCHIVE_HAS_MD5) || defined(ARCHIVE_HAS_RMD160) || \
1601     defined(ARCHIVE_HAS_SHA1) || defined(ARCHIVE_HAS_SHA256) || \
1602     defined(ARCHIVE_HAS_SHA384) || defined(ARCHIVE_HAS_SHA512)
1603 static void
strappend_bin(struct archive_string * s,const unsigned char * bin,int n)1604 strappend_bin(struct archive_string *s, const unsigned char *bin, int n)
1605 {
1606 	static const char hex[] = "0123456789abcdef";
1607 	int i;
1608 
1609 	for (i = 0; i < n; i++) {
1610 		archive_strappend_char(s, hex[bin[i] >> 4]);
1611 		archive_strappend_char(s, hex[bin[i] & 0x0f]);
1612 	}
1613 }
1614 #endif
1615 
1616 static void
sum_write(struct archive_string * str,struct reg_info * reg)1617 sum_write(struct archive_string *str, struct reg_info *reg)
1618 {
1619 
1620 	if (reg->compute_sum & F_CKSUM) {
1621 		archive_string_sprintf(str, " cksum=%ju",
1622 		    (uintmax_t)reg->crc);
1623 	}
1624 #ifdef ARCHIVE_HAS_MD5
1625 	if (reg->compute_sum & F_MD5) {
1626 		archive_strcat(str, " md5digest=");
1627 		strappend_bin(str, reg->buf_md5, sizeof(reg->buf_md5));
1628 	}
1629 #endif
1630 #ifdef ARCHIVE_HAS_RMD160
1631 	if (reg->compute_sum & F_RMD160) {
1632 		archive_strcat(str, " rmd160digest=");
1633 		strappend_bin(str, reg->buf_rmd160, sizeof(reg->buf_rmd160));
1634 	}
1635 #endif
1636 #ifdef ARCHIVE_HAS_SHA1
1637 	if (reg->compute_sum & F_SHA1) {
1638 		archive_strcat(str, " sha1digest=");
1639 		strappend_bin(str, reg->buf_sha1, sizeof(reg->buf_sha1));
1640 	}
1641 #endif
1642 #ifdef ARCHIVE_HAS_SHA256
1643 	if (reg->compute_sum & F_SHA256) {
1644 		archive_strcat(str, " sha256digest=");
1645 		strappend_bin(str, reg->buf_sha256, sizeof(reg->buf_sha256));
1646 	}
1647 #endif
1648 #ifdef ARCHIVE_HAS_SHA384
1649 	if (reg->compute_sum & F_SHA384) {
1650 		archive_strcat(str, " sha384digest=");
1651 		strappend_bin(str, reg->buf_sha384, sizeof(reg->buf_sha384));
1652 	}
1653 #endif
1654 #ifdef ARCHIVE_HAS_SHA512
1655 	if (reg->compute_sum & F_SHA512) {
1656 		archive_strcat(str, " sha512digest=");
1657 		strappend_bin(str, reg->buf_sha512, sizeof(reg->buf_sha512));
1658 	}
1659 #endif
1660 }
1661 
1662 static int
mtree_entry_cmp_node(const struct archive_rb_node * n1,const struct archive_rb_node * n2)1663 mtree_entry_cmp_node(const struct archive_rb_node *n1,
1664     const struct archive_rb_node *n2)
1665 {
1666 	const struct mtree_entry *e1 = (const struct mtree_entry *)n1;
1667 	const struct mtree_entry *e2 = (const struct mtree_entry *)n2;
1668 
1669 	return (strcmp(e2->basename.s, e1->basename.s));
1670 }
1671 
1672 static int
mtree_entry_cmp_key(const struct archive_rb_node * n,const void * key)1673 mtree_entry_cmp_key(const struct archive_rb_node *n, const void *key)
1674 {
1675 	const struct mtree_entry *e = (const struct mtree_entry *)n;
1676 
1677 	return (strcmp((const char *)key, e->basename.s));
1678 }
1679 
1680 #if defined(_WIN32) || defined(__CYGWIN__)
1681 static int
cleanup_backslash_1(char * p)1682 cleanup_backslash_1(char *p)
1683 {
1684 	int mb, dos;
1685 
1686 	mb = dos = 0;
1687 	while (*p) {
1688 		if (*(unsigned char *)p > 127)
1689 			mb = 1;
1690 		if (*p == '\\') {
1691 			/* If we have not met any multi-byte characters,
1692 			 * we can replace '\' with '/'. */
1693 			if (!mb)
1694 				*p = '/';
1695 			dos = 1;
1696 		}
1697 		p++;
1698 	}
1699 	if (!mb || !dos)
1700 		return (0);
1701 	return (-1);
1702 }
1703 
1704 static void
cleanup_backslash_2(wchar_t * p)1705 cleanup_backslash_2(wchar_t *p)
1706 {
1707 
1708 	/* Convert a path-separator from '\' to  '/' */
1709 	while (*p != L'\0') {
1710 		if (*p == L'\\')
1711 			*p = L'/';
1712 		p++;
1713 	}
1714 }
1715 #endif
1716 
1717 /*
1718  * Generate a parent directory name and a base name from a pathname.
1719  */
1720 static int
mtree_entry_setup_filenames(struct archive_write * a,struct mtree_entry * file,struct archive_entry * entry)1721 mtree_entry_setup_filenames(struct archive_write *a, struct mtree_entry *file,
1722     struct archive_entry *entry)
1723 {
1724 	const char *pathname;
1725 	char *p, *dirname, *slash;
1726 	size_t len;
1727 	int ret = ARCHIVE_OK;
1728 
1729 	archive_strcpy(&file->pathname, archive_entry_pathname(entry));
1730 #if defined(_WIN32) || defined(__CYGWIN__)
1731 	/*
1732 	 * Convert a path-separator from '\' to  '/'
1733 	 */
1734 	if (cleanup_backslash_1(file->pathname.s) != 0) {
1735 		const wchar_t *wp = archive_entry_pathname_w(entry);
1736 		struct archive_wstring ws;
1737 
1738 		if (wp != NULL) {
1739 			int r;
1740 			archive_string_init(&ws);
1741 			archive_wstrcpy(&ws, wp);
1742 			cleanup_backslash_2(ws.s);
1743 			archive_string_empty(&(file->pathname));
1744 			r = archive_string_append_from_wcs(&(file->pathname),
1745 			    ws.s, ws.length);
1746 			archive_wstring_free(&ws);
1747 			if (r < 0 && errno == ENOMEM) {
1748 				archive_set_error(&a->archive, ENOMEM,
1749 				    "Can't allocate memory");
1750 				return (ARCHIVE_FATAL);
1751 			}
1752 		}
1753 	}
1754 #else
1755 	(void)a; /* UNUSED */
1756 #endif
1757 	pathname =  file->pathname.s;
1758 	if (strcmp(pathname, ".") == 0) {
1759 		archive_strcpy(&file->basename, ".");
1760 		return (ARCHIVE_OK);
1761 	}
1762 
1763 	archive_strcpy(&(file->parentdir), pathname);
1764 
1765 	len = file->parentdir.length;
1766 	p = dirname = file->parentdir.s;
1767 
1768 	/*
1769 	 * Remove leading '/' and '../' elements
1770 	 */
1771 	while (*p) {
1772 		if (p[0] == '/') {
1773 			p++;
1774 			len--;
1775 		} else if (p[0] != '.')
1776 			break;
1777 		else if (p[1] == '.' && p[2] == '/') {
1778 			p += 3;
1779 			len -= 3;
1780 		} else
1781 			break;
1782 	}
1783 	if (p != dirname) {
1784 		memmove(dirname, p, len+1);
1785 		p = dirname;
1786 	}
1787 	/*
1788 	 * Remove "/","/." and "/.." elements from tail.
1789 	 */
1790 	while (len > 0) {
1791 		size_t ll = len;
1792 
1793 		if (len > 0 && p[len-1] == '/') {
1794 			p[len-1] = '\0';
1795 			len--;
1796 		}
1797 		if (len > 1 && p[len-2] == '/' && p[len-1] == '.') {
1798 			p[len-2] = '\0';
1799 			len -= 2;
1800 		}
1801 		if (len > 2 && p[len-3] == '/' && p[len-2] == '.' &&
1802 		    p[len-1] == '.') {
1803 			p[len-3] = '\0';
1804 			len -= 3;
1805 		}
1806 		if (ll == len)
1807 			break;
1808 	}
1809 	while (*p) {
1810 		if (p[0] == '/') {
1811 			if (p[1] == '/')
1812 				/* Convert '//' --> '/' */
1813 				memmove(p, p+1, strlen(p+1) + 1);
1814 			else if (p[1] == '.' && p[2] == '/')
1815 				/* Convert '/./' --> '/' */
1816 				memmove(p, p+2, strlen(p+2) + 1);
1817 			else if (p[1] == '.' && p[2] == '.' && p[3] == '/') {
1818 				/* Convert 'dir/dir1/../dir2/'
1819 				 *     --> 'dir/dir2/'
1820 				 */
1821 				char *rp = p -1;
1822 				while (rp >= dirname) {
1823 					if (*rp == '/')
1824 						break;
1825 					--rp;
1826 				}
1827 				if (rp > dirname) {
1828 					strcpy(rp, p+3);
1829 					p = rp;
1830 				} else {
1831 					strcpy(dirname, p+4);
1832 					p = dirname;
1833 				}
1834 			} else
1835 				p++;
1836 		} else
1837 			p++;
1838 	}
1839 	p = dirname;
1840 	len = strlen(p);
1841 
1842 	/*
1843 	 * Add "./" prefix.
1844 	 * NOTE: If the pathname does not have a path separator, we have
1845 	 * to add "./" to the head of the pathname because mtree reader
1846 	 * will suppose that it is v1(a.k.a classic) mtree format and
1847 	 * change the directory unexpectedly and so it will make a wrong
1848 	 * path.
1849 	 */
1850 	if (strcmp(p, ".") != 0 && strncmp(p, "./", 2) != 0) {
1851 		struct archive_string as;
1852 		archive_string_init(&as);
1853 		archive_strcpy(&as, "./");
1854 		archive_strncat(&as, p, len);
1855 		archive_string_empty(&file->parentdir);
1856 		archive_string_concat(&file->parentdir, &as);
1857 		archive_string_free(&as);
1858 		p = file->parentdir.s;
1859 		len = archive_strlen(&file->parentdir);
1860 	}
1861 
1862 	/*
1863 	 * Find out the position which points the last position of
1864 	 * path separator('/').
1865 	 */
1866 	slash = NULL;
1867 	for (; *p != '\0'; p++) {
1868 		if (*p == '/')
1869 			slash = p;
1870 	}
1871 	if (slash == NULL) {
1872 		/* The pathname doesn't have a parent directory. */
1873 		file->parentdir.length = len;
1874 		archive_string_copy(&(file->basename), &(file->parentdir));
1875 		archive_string_empty(&(file->parentdir));
1876 		*file->parentdir.s = '\0';
1877 		return (ret);
1878 	}
1879 
1880 	/* Make a basename from file->parentdir.s and slash */
1881 	*slash  = '\0';
1882 	file->parentdir.length = slash - file->parentdir.s;
1883 	archive_strcpy(&(file->basename),  slash + 1);
1884 	return (ret);
1885 }
1886 
1887 static int
mtree_entry_create_virtual_dir(struct archive_write * a,const char * pathname,struct mtree_entry ** m_entry)1888 mtree_entry_create_virtual_dir(struct archive_write *a, const char *pathname,
1889     struct mtree_entry **m_entry)
1890 {
1891 	struct archive_entry *entry;
1892 	struct mtree_entry *file;
1893 	int r;
1894 
1895 	entry = archive_entry_new();
1896 	if (entry == NULL) {
1897 		*m_entry = NULL;
1898 		archive_set_error(&a->archive, ENOMEM,
1899 		    "Can't allocate memory");
1900 		return (ARCHIVE_FATAL);
1901 	}
1902 	archive_entry_copy_pathname(entry, pathname);
1903 	archive_entry_set_mode(entry, AE_IFDIR | 0755);
1904 	archive_entry_set_mtime(entry, time(NULL), 0);
1905 
1906 	r = mtree_entry_new(a, entry, &file);
1907 	archive_entry_free(entry);
1908 	if (r < ARCHIVE_WARN) {
1909 		*m_entry = NULL;
1910 		archive_set_error(&a->archive, ENOMEM,
1911 		    "Can't allocate memory");
1912 		return (ARCHIVE_FATAL);
1913 	}
1914 
1915 	file->dir_info->virtual = 1;
1916 
1917 	*m_entry = file;
1918 	return (ARCHIVE_OK);
1919 }
1920 
1921 static void
mtree_entry_register_add(struct mtree_writer * mtree,struct mtree_entry * file)1922 mtree_entry_register_add(struct mtree_writer *mtree, struct mtree_entry *file)
1923 {
1924         file->next = NULL;
1925         *mtree->file_list.last = file;
1926         mtree->file_list.last = &(file->next);
1927 }
1928 
1929 static void
mtree_entry_register_init(struct mtree_writer * mtree)1930 mtree_entry_register_init(struct mtree_writer *mtree)
1931 {
1932 	mtree->file_list.first = NULL;
1933 	mtree->file_list.last = &(mtree->file_list.first);
1934 }
1935 
1936 static void
mtree_entry_register_free(struct mtree_writer * mtree)1937 mtree_entry_register_free(struct mtree_writer *mtree)
1938 {
1939 	struct mtree_entry *file, *file_next;
1940 
1941 	file = mtree->file_list.first;
1942 	while (file != NULL) {
1943 		file_next = file->next;
1944 		mtree_entry_free(file);
1945 		file = file_next;
1946 	}
1947 }
1948 
1949 static int
mtree_entry_add_child_tail(struct mtree_entry * parent,struct mtree_entry * child)1950 mtree_entry_add_child_tail(struct mtree_entry *parent,
1951     struct mtree_entry *child)
1952 {
1953 	child->dir_info->chnext = NULL;
1954 	*parent->dir_info->children.last = child;
1955 	parent->dir_info->children.last = &(child->dir_info->chnext);
1956 	return (1);
1957 }
1958 
1959 /*
1960  * Find a entry from a parent entry with the name.
1961  */
1962 static struct mtree_entry *
mtree_entry_find_child(struct mtree_entry * parent,const char * child_name)1963 mtree_entry_find_child(struct mtree_entry *parent, const char *child_name)
1964 {
1965 	struct mtree_entry *np;
1966 
1967 	if (parent == NULL)
1968 		return (NULL);
1969 	np = (struct mtree_entry *)__archive_rb_tree_find_node(
1970 	    &(parent->dir_info->rbtree), child_name);
1971 	return (np);
1972 }
1973 
1974 static int
get_path_component(char * name,size_t n,const char * fn)1975 get_path_component(char *name, size_t n, const char *fn)
1976 {
1977 	char *p;
1978 	size_t l;
1979 
1980 	p = strchr(fn, '/');
1981 	if (p == NULL) {
1982 		if ((l = strlen(fn)) == 0)
1983 			return (0);
1984 	} else
1985 		l = p - fn;
1986 	if (l > n -1)
1987 		return (-1);
1988 	memcpy(name, fn, l);
1989 	name[l] = '\0';
1990 
1991 	return ((int)l);
1992 }
1993 
1994 /*
1995  * Add a new entry into the tree.
1996  */
1997 static int
mtree_entry_tree_add(struct archive_write * a,struct mtree_entry ** filep)1998 mtree_entry_tree_add(struct archive_write *a, struct mtree_entry **filep)
1999 {
2000 #if defined(_WIN32) && !defined(__CYGWIN__)
2001 	char name[_MAX_FNAME];/* Included null terminator size. */
2002 #elif defined(NAME_MAX) && NAME_MAX >= 255
2003 	char name[NAME_MAX+1];
2004 #else
2005 	char name[256];
2006 #endif
2007 	struct mtree_writer *mtree = (struct mtree_writer *)a->format_data;
2008 	struct mtree_entry *dent, *file, *np;
2009 	const char *fn, *p;
2010 	int l, r;
2011 
2012 	file = *filep;
2013 	if (file->parentdir.length == 0 && file->basename.length == 1 &&
2014 	    file->basename.s[0] == '.') {
2015 		file->parent = file;
2016 		if (mtree->root != NULL) {
2017 			np = mtree->root;
2018 			goto same_entry;
2019 		}
2020 		mtree->root = file;
2021 		mtree_entry_register_add(mtree, file);
2022 		return (ARCHIVE_OK);
2023 	}
2024 
2025 	if (file->parentdir.length == 0) {
2026 		archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
2027 		    "Internal programing error "
2028 		    "in generating canonical name for %s",
2029 		    file->pathname.s);
2030 		return (ARCHIVE_FAILED);
2031 	}
2032 
2033 	fn = p = file->parentdir.s;
2034 
2035 	/*
2036 	 * If the path of the parent directory of `file' entry is
2037 	 * the same as the path of `cur_dirent', add `file' entry to
2038 	 * `cur_dirent'.
2039 	 */
2040 	if (archive_strlen(&(mtree->cur_dirstr))
2041 	      == archive_strlen(&(file->parentdir)) &&
2042 	    strcmp(mtree->cur_dirstr.s, fn) == 0) {
2043 		if (!__archive_rb_tree_insert_node(
2044 		    &(mtree->cur_dirent->dir_info->rbtree),
2045 		    (struct archive_rb_node *)file)) {
2046 			/* There is the same name in the tree. */
2047 			np = (struct mtree_entry *)__archive_rb_tree_find_node(
2048 			    &(mtree->cur_dirent->dir_info->rbtree),
2049 			    file->basename.s);
2050 			goto same_entry;
2051 		}
2052 		file->parent = mtree->cur_dirent;
2053 		mtree_entry_register_add(mtree, file);
2054 		return (ARCHIVE_OK);
2055 	}
2056 
2057 	dent = mtree->root;
2058 	for (;;) {
2059 		l = get_path_component(name, sizeof(name), fn);
2060 		if (l == 0) {
2061 			np = NULL;
2062 			break;
2063 		}
2064 		if (l < 0) {
2065 			archive_set_error(&a->archive,
2066 			    ARCHIVE_ERRNO_MISC,
2067 			    "A name buffer is too small");
2068 			return (ARCHIVE_FATAL);
2069 		}
2070 		if (l == 1 && name[0] == '.' && dent != NULL &&
2071 		    dent == mtree->root) {
2072 			fn += l;
2073 			if (fn[0] == '/')
2074 				fn++;
2075 			continue;
2076 		}
2077 
2078 		np = mtree_entry_find_child(dent, name);
2079 		if (np == NULL || fn[0] == '\0')
2080 			break;
2081 
2082 		/* Find next sub directory. */
2083 		if (!np->dir_info) {
2084 			/* NOT Directory! */
2085 			archive_set_error(&a->archive,
2086 			    ARCHIVE_ERRNO_MISC,
2087 			    "`%s' is not directory, we cannot insert `%s' ",
2088 			    np->pathname.s, file->pathname.s);
2089 			return (ARCHIVE_FAILED);
2090 		}
2091 		fn += l;
2092 		if (fn[0] == '/')
2093 			fn++;
2094 		dent = np;
2095 	}
2096 	if (np == NULL) {
2097 		/*
2098 		 * Create virtual parent directories.
2099 		 */
2100 		while (fn[0] != '\0') {
2101 			struct mtree_entry *vp;
2102 			struct archive_string as;
2103 
2104 			archive_string_init(&as);
2105 			archive_strncat(&as, p, fn - p + l);
2106 			if (as.s[as.length-1] == '/') {
2107 				as.s[as.length-1] = '\0';
2108 				as.length--;
2109 			}
2110 			r = mtree_entry_create_virtual_dir(a, as.s, &vp);
2111 			archive_string_free(&as);
2112 			if (r < ARCHIVE_WARN)
2113 				return (r);
2114 
2115 			if (strcmp(vp->pathname.s, ".") == 0) {
2116 				vp->parent = vp;
2117 				mtree->root = vp;
2118 			} else {
2119 				__archive_rb_tree_insert_node(
2120 				    &(dent->dir_info->rbtree),
2121 				    (struct archive_rb_node *)vp);
2122 				vp->parent = dent;
2123 			}
2124 			mtree_entry_register_add(mtree, vp);
2125 			np = vp;
2126 
2127 			fn += l;
2128 			if (fn[0] == '/')
2129 				fn++;
2130 			l = get_path_component(name, sizeof(name), fn);
2131 			if (l < 0) {
2132 				archive_string_free(&as);
2133 				archive_set_error(&a->archive,
2134 				    ARCHIVE_ERRNO_MISC,
2135 				    "A name buffer is too small");
2136 				return (ARCHIVE_FATAL);
2137 			}
2138 			dent = np;
2139 		}
2140 
2141 		/* Found out the parent directory where `file' can be
2142 		 * inserted. */
2143 		mtree->cur_dirent = dent;
2144 		archive_string_empty(&(mtree->cur_dirstr));
2145 		archive_string_ensure(&(mtree->cur_dirstr),
2146 		    archive_strlen(&(dent->parentdir)) +
2147 		    archive_strlen(&(dent->basename)) + 2);
2148 		if (archive_strlen(&(dent->parentdir)) +
2149 		    archive_strlen(&(dent->basename)) == 0)
2150 			mtree->cur_dirstr.s[0] = 0;
2151 		else {
2152 			if (archive_strlen(&(dent->parentdir)) > 0) {
2153 				archive_string_copy(&(mtree->cur_dirstr),
2154 				    &(dent->parentdir));
2155 				archive_strappend_char(
2156 				    &(mtree->cur_dirstr), '/');
2157 			}
2158 			archive_string_concat(&(mtree->cur_dirstr),
2159 			    &(dent->basename));
2160 		}
2161 
2162 		if (!__archive_rb_tree_insert_node(
2163 		    &(dent->dir_info->rbtree),
2164 		    (struct archive_rb_node *)file)) {
2165 			np = (struct mtree_entry *)__archive_rb_tree_find_node(
2166 			    &(dent->dir_info->rbtree), file->basename.s);
2167 			goto same_entry;
2168 		}
2169 		file->parent = dent;
2170 		mtree_entry_register_add(mtree, file);
2171 		return (ARCHIVE_OK);
2172 	}
2173 
2174 same_entry:
2175 	/*
2176 	 * We have already has the entry the filename of which is
2177 	 * the same.
2178 	 */
2179 	r = mtree_entry_exchange_same_entry(a, np, file);
2180 	if (r < ARCHIVE_WARN)
2181 		return (r);
2182 	if (np->dir_info)
2183 		np->dir_info->virtual = 0;
2184 	*filep = np;
2185 	mtree_entry_free(file);
2186 	return (ARCHIVE_WARN);
2187 }
2188 
2189 static int
mtree_entry_exchange_same_entry(struct archive_write * a,struct mtree_entry * np,struct mtree_entry * file)2190 mtree_entry_exchange_same_entry(struct archive_write *a, struct mtree_entry *np,
2191     struct mtree_entry *file)
2192 {
2193 
2194 	if ((np->mode & AE_IFMT) != (file->mode & AE_IFMT)) {
2195 		archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
2196 		    "Found duplicate entries `%s' and its file type is "
2197 		    "different",
2198 		    np->pathname.s);
2199 		return (ARCHIVE_FAILED);
2200 	}
2201 
2202 	/* Update the existent mtree entry's attributes by the new one's. */
2203 	archive_string_empty(&np->symlink);
2204 	archive_string_concat(&np->symlink, &file->symlink);
2205 	archive_string_empty(&np->uname);
2206 	archive_string_concat(&np->uname, &file->uname);
2207 	archive_string_empty(&np->gname);
2208 	archive_string_concat(&np->gname, &file->gname);
2209 	archive_string_empty(&np->fflags_text);
2210 	archive_string_concat(&np->fflags_text, &file->fflags_text);
2211 	np->nlink = file->nlink;
2212 	np->filetype = file->filetype;
2213 	np->mode = file->mode;
2214 	np->size = file->size;
2215 	np->uid = file->uid;
2216 	np->gid = file->gid;
2217 	np->fflags_set = file->fflags_set;
2218 	np->fflags_clear = file->fflags_clear;
2219 	np->mtime = file->mtime;
2220 	np->mtime_nsec = file->mtime_nsec;
2221 	np->rdevmajor = file->rdevmajor;
2222 	np->rdevminor = file->rdevminor;
2223 	np->devmajor = file->devmajor;
2224 	np->devminor = file->devminor;
2225 	np->ino = file->ino;
2226 
2227 	return (ARCHIVE_WARN);
2228 }
2229