2 * Create a squashfs filesystem. This is a highly compressed read only
5 * Copyright (c) 2008, 2009, 2010, 2012, 2014, 2019
6 * Phillip Lougher <phillip@squashfs.org.uk>
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version 2,
11 * or (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
30 #include <sys/types.h>
37 #include <sys/xattr.h>
39 #include "squashfs_fs.h"
40 #include "squashfs_swap.h"
41 #include "mksquashfs.h"
44 #include "progressbar.h"
46 /* compressed xattr table */
47 static char *xattr_table
= NULL
;
48 static unsigned int xattr_size
= 0;
50 /* cached uncompressed xattr data */
51 static char *data_cache
= NULL
;
52 static int cache_bytes
= 0, cache_size
= 0;
54 /* cached uncompressed xattr id table */
55 static struct squashfs_xattr_id
*xattr_id_table
= NULL
;
56 static int xattr_ids
= 0;
58 /* saved compressed xattr table */
59 unsigned int sxattr_bytes
= 0, stotal_xattr_bytes
= 0;
61 /* saved cached uncompressed xattr data */
62 static char *sdata_cache
= NULL
;
63 static int scache_bytes
= 0;
65 /* saved cached uncompressed xattr id table */
66 static int sxattr_ids
= 0;
68 /* xattr hash table for value duplicate detection */
69 static struct xattr_list
*dupl_value
[65536];
71 /* xattr hash table for id duplicate detection */
72 static struct dupl_id
*dupl_id
[65536];
74 /* file system globals from mksquashfs.c */
75 extern int no_xattrs
, noX
;
76 extern long long bytes
;
78 extern unsigned int xattr_bytes
, total_xattr_bytes
;
80 /* helper functions from mksquashfs.c */
81 extern unsigned short get_checksum(char *, int, unsigned short);
82 extern void write_destination(int, long long, int, void *);
83 extern long long generic_write_table(int, void *, int, void *, int);
84 extern int mangle(char *, char *, int, int, int, int);
85 extern char *pathname(struct dir_ent
*);
87 /* helper functions and definitions from read_xattrs.c */
88 extern int read_xattrs_from_disk(int, struct squashfs_super_block
*, int, long long *);
89 extern struct xattr_list
*get_xattr(int, unsigned int *, int *);
90 extern struct prefix prefix_table
[];
93 static int get_prefix(struct xattr_list
*xattr
, char *name
)
97 xattr
->full_name
= strdup(name
);
99 for(i
= 0; prefix_table
[i
].type
!= -1; i
++) {
100 struct prefix
*p
= &prefix_table
[i
];
101 if(strncmp(xattr
->full_name
, p
->prefix
, strlen(p
->prefix
)) == 0)
105 if(prefix_table
[i
].type
!= -1) {
106 xattr
->name
= xattr
->full_name
+ strlen(prefix_table
[i
].prefix
);
107 xattr
->size
= strlen(xattr
->name
);
110 return prefix_table
[i
].type
;
114 static int read_xattrs_from_system(char *filename
, struct xattr_list
**xattrs
)
117 char *xattr_names
, *p
;
119 struct xattr_list
*xattr_list
= NULL
;
122 size
= llistxattr(filename
, NULL
, 0);
124 if(size
< 0 && errno
!= ENOTSUP
) {
125 ERROR_START("llistxattr for %s failed in "
126 "read_attrs, because %s", filename
,
128 ERROR_EXIT(". Ignoring");
133 xattr_names
= malloc(size
);
134 if(xattr_names
== NULL
)
137 size
= llistxattr(filename
, xattr_names
, size
);
141 /* xattr list grew? Try again */
144 ERROR_START("llistxattr for %s failed in "
145 "read_attrs, because %s", filename
,
147 ERROR_EXIT(". Ignoring");
155 for(i
= 0, p
= xattr_names
; p
< xattr_names
+ size
; i
++) {
156 struct xattr_list
*x
= realloc(xattr_list
, (i
+ 1) *
157 sizeof(struct xattr_list
));
162 xattr_list
[i
].type
= get_prefix(&xattr_list
[i
], p
);
164 if(xattr_list
[i
].type
== -1) {
165 ERROR("Unrecognised xattr prefix %s\n",
166 xattr_list
[i
].full_name
);
167 free(xattr_list
[i
].full_name
);
173 vsize
= lgetxattr(filename
, xattr_list
[i
].full_name
,
176 ERROR_START("lgetxattr failed for %s in "
177 "read_attrs, because %s", filename
,
179 ERROR_EXIT(". Ignoring");
180 free(xattr_list
[i
].full_name
);
184 xattr_list
[i
].value
= malloc(vsize
);
185 if(xattr_list
[i
].value
== NULL
)
188 vsize
= lgetxattr(filename
, xattr_list
[i
].full_name
,
189 xattr_list
[i
].value
, vsize
);
191 free(xattr_list
[i
].value
);
193 /* xattr grew? Try again */
196 ERROR_START("lgetxattr failed for %s "
197 "in read_attrs, because %s",
198 filename
, strerror(errno
));
199 ERROR_EXIT(". Ignoring");
200 free(xattr_list
[i
].full_name
);
207 xattr_list
[i
].vsize
= vsize
;
209 TRACE("read_xattrs_from_system: filename %s, xattr name %s,"
210 " vsize %d\n", filename
, xattr_list
[i
].full_name
,
211 xattr_list
[i
].vsize
);
215 *xattrs
= xattr_list
;
222 free(xattr_list
[i
].full_name
);
223 free(xattr_list
[i
].value
);
231 static int get_xattr_size(struct xattr_list
*xattr
)
233 int size
= sizeof(struct squashfs_xattr_entry
) +
234 sizeof(struct squashfs_xattr_val
) + xattr
->size
;
236 if(xattr
->type
& XATTR_VALUE_OOL
)
237 size
+= XATTR_VALUE_OOL_SIZE
;
239 size
+= xattr
->vsize
;
245 static void *get_xattr_space(unsigned int req_size
, long long *disk
)
248 unsigned short c_byte
;
251 * Move and compress cached uncompressed data into xattr table.
253 while(cache_bytes
>= SQUASHFS_METADATA_SIZE
) {
254 if((xattr_size
- xattr_bytes
) <
255 ((SQUASHFS_METADATA_SIZE
<< 1)) + 2) {
256 xattr_table
= realloc(xattr_table
, xattr_size
+
257 (SQUASHFS_METADATA_SIZE
<< 1) + 2);
258 if(xattr_table
== NULL
)
260 xattr_size
+= (SQUASHFS_METADATA_SIZE
<< 1) + 2;
263 c_byte
= mangle(xattr_table
+ xattr_bytes
+ BLOCK_OFFSET
,
264 data_cache
, SQUASHFS_METADATA_SIZE
,
265 SQUASHFS_METADATA_SIZE
, noX
, 0);
266 TRACE("Xattr block @ 0x%x, size %d\n", xattr_bytes
, c_byte
);
267 SQUASHFS_SWAP_SHORTS(&c_byte
, xattr_table
+ xattr_bytes
, 1);
268 xattr_bytes
+= SQUASHFS_COMPRESSED_SIZE(c_byte
) + BLOCK_OFFSET
;
269 memmove(data_cache
, data_cache
+ SQUASHFS_METADATA_SIZE
,
270 cache_bytes
- SQUASHFS_METADATA_SIZE
);
271 cache_bytes
-= SQUASHFS_METADATA_SIZE
;
275 * Ensure there's enough space in the uncompressed data cache
277 data_space
= cache_size
- cache_bytes
;
278 if(data_space
< req_size
) {
279 int realloc_size
= req_size
- data_space
;
280 data_cache
= realloc(data_cache
, cache_size
+
282 if(data_cache
== NULL
)
284 cache_size
+= realloc_size
;
288 *disk
= ((long long) xattr_bytes
<< 16) | cache_bytes
;
289 cache_bytes
+= req_size
;
290 return data_cache
+ cache_bytes
- req_size
;
294 static struct dupl_id
*check_id_dupl(struct xattr_list
*xattr_list
, int xattrs
)
296 struct dupl_id
*entry
;
298 unsigned short checksum
= 0;
300 /* compute checksum over all xattrs */
301 for(i
= 0; i
< xattrs
; i
++) {
302 struct xattr_list
*xattr
= &xattr_list
[i
];
304 checksum
= get_checksum(xattr
->full_name
,
305 strlen(xattr
->full_name
), checksum
);
306 checksum
= get_checksum(xattr
->value
,
307 xattr
->vsize
, checksum
);
310 for(entry
= dupl_id
[checksum
]; entry
; entry
= entry
->next
) {
311 if (entry
->xattrs
!= xattrs
)
314 for(i
= 0; i
< xattrs
; i
++) {
315 struct xattr_list
*xattr
= &xattr_list
[i
];
316 struct xattr_list
*dup_xattr
= &entry
->xattr_list
[i
];
318 if(strcmp(xattr
->full_name
, dup_xattr
->full_name
))
321 if(xattr
->vsize
!= dup_xattr
->vsize
)
324 if(memcmp(xattr
->value
, dup_xattr
->value
, xattr
->vsize
))
333 /* no duplicate exists */
334 entry
= malloc(sizeof(*entry
));
337 entry
->xattrs
= xattrs
;
338 entry
->xattr_list
= xattr_list
;
339 entry
->xattr_id
= SQUASHFS_INVALID_XATTR
;
340 entry
->next
= dupl_id
[checksum
];
341 dupl_id
[checksum
] = entry
;
348 static void check_value_dupl(struct xattr_list
*xattr
)
350 struct xattr_list
*entry
;
352 if(xattr
->vsize
< XATTR_VALUE_OOL_SIZE
)
355 /* Check if this is a duplicate of an existing value */
356 xattr
->vchecksum
= get_checksum(xattr
->value
, xattr
->vsize
, 0);
357 for(entry
= dupl_value
[xattr
->vchecksum
]; entry
; entry
= entry
->vnext
) {
358 if(entry
->vsize
!= xattr
->vsize
)
361 if(memcmp(entry
->value
, xattr
->value
, xattr
->vsize
) == 0)
367 * No duplicate exists, add to hash table, and mark as
370 xattr
->vnext
= dupl_value
[xattr
->vchecksum
];
371 dupl_value
[xattr
->vchecksum
] = xattr
;
372 xattr
->ool_value
= SQUASHFS_INVALID_BLK
;
375 * Duplicate exists, make type XATTR_VALUE_OOL, and
376 * remember where the duplicate is
378 xattr
->type
|= XATTR_VALUE_OOL
;
379 xattr
->ool_value
= entry
->ool_value
;
380 /* on appending don't free duplicate values because the
381 * duplicate value already points to the non-duplicate value */
382 if(xattr
->value
!= entry
->value
) {
384 xattr
->value
= entry
->value
;
390 static int get_xattr_id(int xattrs
, struct xattr_list
*xattr_list
,
391 long long xattr_disk
, struct dupl_id
*xattr_dupl
)
394 struct squashfs_xattr_id
*xattr_id
;
396 xattr_id_table
= realloc(xattr_id_table
, (xattr_ids
+ 1) *
397 sizeof(struct squashfs_xattr_id
));
398 if(xattr_id_table
== NULL
)
401 /* get total uncompressed size of xattr data, needed for stat */
402 for(i
= 0; i
< xattrs
; i
++)
403 size
+= strlen(xattr_list
[i
].full_name
) + 1 +
406 xattr_id
= &xattr_id_table
[xattr_ids
];
407 xattr_id
->xattr
= xattr_disk
;
408 xattr_id
->count
= xattrs
;
409 xattr_id
->size
= size
;
412 * keep track of total uncompressed xattr data, needed for mksquashfs
413 * file system summary
415 total_xattr_bytes
+= size
;
417 xattr_dupl
->xattr_id
= xattr_ids
++;
418 return xattr_dupl
->xattr_id
;
422 long long write_xattrs()
424 unsigned short c_byte
;
426 char *datap
= data_cache
;
427 long long start_bytes
= bytes
;
428 struct squashfs_xattr_table header
;
431 return SQUASHFS_INVALID_BLK
;
434 * Move and compress cached uncompressed data into xattr table.
437 if((xattr_size
- xattr_bytes
) <
438 ((SQUASHFS_METADATA_SIZE
<< 1)) + 2) {
439 xattr_table
= realloc(xattr_table
, xattr_size
+
440 (SQUASHFS_METADATA_SIZE
<< 1) + 2);
441 if(xattr_table
== NULL
)
443 xattr_size
+= (SQUASHFS_METADATA_SIZE
<< 1) + 2;
446 avail_bytes
= cache_bytes
> SQUASHFS_METADATA_SIZE
?
447 SQUASHFS_METADATA_SIZE
: cache_bytes
;
448 c_byte
= mangle(xattr_table
+ xattr_bytes
+ BLOCK_OFFSET
, datap
,
449 avail_bytes
, SQUASHFS_METADATA_SIZE
, noX
, 0);
450 TRACE("Xattr block @ 0x%x, size %d\n", xattr_bytes
, c_byte
);
451 SQUASHFS_SWAP_SHORTS(&c_byte
, xattr_table
+ xattr_bytes
, 1);
452 xattr_bytes
+= SQUASHFS_COMPRESSED_SIZE(c_byte
) + BLOCK_OFFSET
;
453 datap
+= avail_bytes
;
454 cache_bytes
-= avail_bytes
;
458 * Write compressed xattr table to file system
460 write_destination(fd
, bytes
, xattr_bytes
, xattr_table
);
461 bytes
+= xattr_bytes
;
464 * Swap if necessary the xattr id table
466 for(i
= 0; i
< xattr_ids
; i
++)
467 SQUASHFS_INSWAP_XATTR_ID(&xattr_id_table
[i
]);
469 header
.xattr_ids
= xattr_ids
;
470 header
.xattr_table_start
= start_bytes
;
471 SQUASHFS_INSWAP_XATTR_TABLE(&header
);
473 return generic_write_table(xattr_ids
* sizeof(struct squashfs_xattr_id
),
474 xattr_id_table
, sizeof(header
), &header
, noX
);
478 int generate_xattrs(int xattrs
, struct xattr_list
*xattr_list
)
483 long long xattr_disk
;
484 struct dupl_id
*xattr_dupl
;
487 * check if the file xattrs are a complete duplicate of a pre-existing
490 xattr_dupl
= check_id_dupl(xattr_list
, xattrs
);
491 if(xattr_dupl
->xattr_id
!= SQUASHFS_INVALID_XATTR
)
492 return xattr_dupl
->xattr_id
;
495 * Scan the xattr_list deciding which type to assign to each
496 * xattr. The choice is fairly straightforward, and depends on the
497 * size of each xattr name/value and the overall size of the
498 * resultant xattr list stored in the xattr metadata table.
500 * Choices are whether to store data inline or out of line.
502 * The overall goal is to optimise xattr scanning and lookup, and
503 * to enable the file system layout to scale from a couple of
504 * small xattr name/values to a large number of large xattr
505 * names/values without affecting performance. While hopefully
506 * enabling the common case of a couple of small xattr name/values
507 * to be stored efficiently
509 * Code repeatedly scans, doing the following
510 * move xattr data out of line if it exceeds
511 * xattr_value_max. Where xattr_value_max is
512 * initially XATTR_INLINE_MAX. If the final uncompressed
513 * xattr list is larger than XATTR_TARGET_MAX then more
514 * aggressively move xattr data out of line by repeatedly
515 * setting inline threshold to 1/2, then 1/4, 1/8 of
516 * XATTR_INLINE_MAX until target achieved or there's
517 * nothing left to move out of line
519 xattr_value_max
= XATTR_INLINE_MAX
;
521 for(total_size
= 0, i
= 0; i
< xattrs
; i
++) {
522 struct xattr_list
*xattr
= &xattr_list
[i
];
523 xattr
->type
&= XATTR_PREFIX_MASK
; /* all inline */
524 if (xattr
->vsize
> xattr_value_max
)
525 xattr
->type
|= XATTR_VALUE_OOL
;
527 total_size
+= get_xattr_size(xattr
);
531 * If the total size of the uncompressed xattr list is <=
532 * XATTR_TARGET_MAX we're done
534 if(total_size
<= XATTR_TARGET_MAX
)
537 if(xattr_value_max
== XATTR_VALUE_OOL_SIZE
)
541 * Inline target not yet at minimum and so reduce it, and
544 xattr_value_max
/= 2;
545 if(xattr_value_max
< XATTR_VALUE_OOL_SIZE
)
546 xattr_value_max
= XATTR_VALUE_OOL_SIZE
;
550 * Check xattr values for duplicates
552 for(i
= 0; i
< xattrs
; i
++) {
553 check_value_dupl(&xattr_list
[i
]);
557 * Add each out of line value to the file system xattr table
558 * if it doesn't already exist as a duplicate
560 for(i
= 0; i
< xattrs
; i
++) {
561 struct xattr_list
*xattr
= &xattr_list
[i
];
563 if((xattr
->type
& XATTR_VALUE_OOL
) &&
564 (xattr
->ool_value
== SQUASHFS_INVALID_BLK
)) {
565 struct squashfs_xattr_val val
;
566 int size
= sizeof(val
) + xattr
->vsize
;
567 xp
= get_xattr_space(size
, &xattr
->ool_value
);
568 val
.vsize
= xattr
->vsize
;
569 SQUASHFS_SWAP_XATTR_VAL(&val
, xp
);
570 memcpy(xp
+ sizeof(val
), xattr
->value
, xattr
->vsize
);
575 * Create xattr list and add to file system xattr table
577 get_xattr_space(0, &xattr_disk
);
578 for(i
= 0; i
< xattrs
; i
++) {
579 struct xattr_list
*xattr
= &xattr_list
[i
];
580 struct squashfs_xattr_entry entry
;
581 struct squashfs_xattr_val val
;
583 xp
= get_xattr_space(sizeof(entry
) + xattr
->size
, NULL
);
584 entry
.type
= xattr
->type
;
585 entry
.size
= xattr
->size
;
586 SQUASHFS_SWAP_XATTR_ENTRY(&entry
, xp
);
587 memcpy(xp
+ sizeof(entry
), xattr
->name
, xattr
->size
);
589 if(xattr
->type
& XATTR_VALUE_OOL
) {
590 int size
= sizeof(val
) + XATTR_VALUE_OOL_SIZE
;
591 xp
= get_xattr_space(size
, NULL
);
592 val
.vsize
= XATTR_VALUE_OOL_SIZE
;
593 SQUASHFS_SWAP_XATTR_VAL(&val
, xp
);
594 SQUASHFS_SWAP_LONG_LONGS(&xattr
->ool_value
, xp
+
597 int size
= sizeof(val
) + xattr
->vsize
;
598 xp
= get_xattr_space(size
, &xattr
->ool_value
);
599 val
.vsize
= xattr
->vsize
;
600 SQUASHFS_SWAP_XATTR_VAL(&val
, xp
);
601 memcpy(xp
+ sizeof(val
), xattr
->value
, xattr
->vsize
);
606 * Add to xattr id lookup table
608 return get_xattr_id(xattrs
, xattr_list
, xattr_disk
, xattr_dupl
);
612 int read_xattrs(void *d
)
614 struct dir_ent
*dir_ent
= d
;
615 struct inode_info
*inode
= dir_ent
->inode
;
616 char *filename
= pathname(dir_ent
);
617 struct xattr_list
*xattr_list
;
620 if(no_xattrs
|| IS_PSEUDO(inode
) || inode
->root_entry
)
621 return SQUASHFS_INVALID_XATTR
;
623 xattrs
= read_xattrs_from_system(filename
, &xattr_list
);
625 return SQUASHFS_INVALID_XATTR
;
627 return generate_xattrs(xattrs
, xattr_list
);
632 * Add the existing xattr ids and xattr metadata in the file system being
633 * appended to, to the in-memory xattr cache. This allows duplicate checking to
634 * take place against the xattrs already in the file system being appended to,
635 * and ensures the pre-existing xattrs are written out along with any new xattrs
637 int get_xattrs(int fd
, struct squashfs_super_block
*sBlk
)
642 TRACE("get_xattrs\n");
644 res
= read_xattrs_from_disk(fd
, sBlk
, FALSE
, NULL
);
645 if(res
== SQUASHFS_INVALID_BLK
|| res
== 0)
650 * for each xattr id read and construct its list of xattr
651 * name:value pairs, and add them to the in-memory xattr cache
653 for(i
= 0; i
< ids
; i
++) {
654 struct xattr_list
*xattr_list
= get_xattr(i
, &count
, &res
);
656 free_xattr(xattr_list
, count
);
659 id
= generate_xattrs(count
, xattr_list
);
662 * Sanity check, the new xattr id should be the same as the
663 * xattr id in the original file system
666 ERROR("BUG, different xattr_id in get_xattrs\n");
678 * Save current state of xattrs, needed for restoring state in the event of an
683 /* save the current state of the compressed xattr data */
684 sxattr_bytes
= xattr_bytes
;
685 stotal_xattr_bytes
= total_xattr_bytes
;
688 * save the current state of the cached uncompressed xattr data.
689 * Note we have to save the contents of the data cache because future
690 * operations will delete the current contents
692 sdata_cache
= malloc(cache_bytes
);
693 if(sdata_cache
== NULL
)
696 memcpy(sdata_cache
, data_cache
, cache_bytes
);
697 scache_bytes
= cache_bytes
;
699 /* save the current state of the xattr id table */
700 sxattr_ids
= xattr_ids
;
705 * Restore xattrs in the event of an abort in appending
707 void restore_xattrs()
709 /* restore the state of the compressed xattr data */
710 xattr_bytes
= sxattr_bytes
;
711 total_xattr_bytes
= stotal_xattr_bytes
;
713 /* restore the state of the uncomoressed xattr data */
714 memcpy(data_cache
, sdata_cache
, scache_bytes
);
715 cache_bytes
= scache_bytes
;
717 /* restore the state of the xattr id table */
718 xattr_ids
= sxattr_ids
;