1 /*
2  * Copyright (c) 2007 Vreixo Formoso
3  * Copyright (c) 2009 - 2016 Thomas Schmitt
4  *
5  * This file is part of the libisofs project; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License version 2
7  * or later as published by the Free Software Foundation.
8  * See COPYING file for details.
9  */
10 
11 #ifdef HAVE_CONFIG_H
12 #include "../config.h"
13 #endif
14 
15 /* Must be before ecma119.h because of eventual Libisofs_with_rrip_rR */
16 #include "libisofs.h"
17 
18 #include "ecma119_tree.h"
19 #include "ecma119.h"
20 #include "node.h"
21 #include "util.h"
22 #include "filesrc.h"
23 #include "messages.h"
24 #include "image.h"
25 #include "stream.h"
26 #include "eltorito.h"
27 
28 #include <stdlib.h>
29 #include <string.h>
30 #include <stdio.h>
31 
32 /* @param flag   bit0=  Do not issue error messages
33 */
iso_get_ecma119_name(IsoWriteOpts * opts,char * input_charset,int imgid,char * node_name,enum IsoNodeType node_type,char ** name,int flag)34 int iso_get_ecma119_name(IsoWriteOpts *opts, char *input_charset, int imgid,
35                          char *node_name, enum IsoNodeType node_type,
36                          char **name, int flag)
37 {
38     int ret, relaxed, free_ascii_name = 0, force_dots = 0;
39     char *ascii_name;
40     char *isoname = NULL;
41 
42     if (node_name == NULL) {
43         /* it is not necessarily an error, it can be the root */
44         return ISO_SUCCESS;
45     }
46 
47     if (opts->untranslated_name_len > 0) {
48         ascii_name = node_name;
49         ret = 1;
50     } else {
51         ret = str2ascii(input_charset, node_name, &ascii_name);
52         free_ascii_name = 1;
53     }
54     if (ret < 0) {
55         if (!(flag & 512))
56             iso_msg_submit(imgid, ret, 0,
57                            "Cannot convert name '%s' to ASCII", node_name);
58         return ret;
59     }
60 
61     if (opts->allow_full_ascii) {
62         relaxed = 2;
63     } else {
64         relaxed = (int)opts->allow_lowercase;
65     }
66     if (opts->allow_7bit_ascii)
67         relaxed |= 4;
68     if (node_type == LIBISO_DIR && !(opts->allow_dir_id_ext)) {
69         if (opts->untranslated_name_len > 0) {
70             if (strlen(ascii_name) > opts->untranslated_name_len) {
71 needs_transl:;
72                 if (!(flag & 512))
73                     iso_msg_submit(imgid, ISO_NAME_NEEDS_TRANSL, 0,
74               "File name too long (%d > %d) for untranslated recording:  '%s'",
75                           strlen(ascii_name), opts->untranslated_name_len,
76                           ascii_name);
77                 return ISO_NAME_NEEDS_TRANSL;
78             }
79             isoname = strdup(ascii_name);
80         } else if (opts->max_37_char_filenames) {
81             isoname = iso_r_dirid(ascii_name, 37, relaxed);
82         } else if (opts->iso_level == 1) {
83 
84 #ifdef Libisofs_old_ecma119_nameS
85 
86             if (relaxed) {
87                 isoname = iso_r_dirid(ascii_name, 8, relaxed);
88             } else {
89                 isoname = iso_1_dirid(ascii_name, 0);
90             }
91 
92 #else /* Libisofs_old_ecma119_nameS */
93 
94             isoname = iso_1_dirid(ascii_name, relaxed);
95 
96 #endif /* ! Libisofs_old_ecma119_nameS */
97 
98 
99         } else {
100             if (relaxed) {
101                 isoname = iso_r_dirid(ascii_name, 31, relaxed);
102             } else {
103                 isoname = iso_2_dirid(ascii_name);
104             }
105         }
106     } else {
107         force_dots = !((opts->no_force_dots & 1) ||
108                        node_type == LIBISO_DIR);
109         if (opts->untranslated_name_len > 0) {
110             if (strlen(ascii_name) > opts->untranslated_name_len)
111                 goto needs_transl;
112             isoname = strdup(ascii_name);
113         } else if (opts->max_37_char_filenames) {
114             isoname = iso_r_fileid(ascii_name, 36, relaxed, force_dots);
115         } else if (opts->iso_level == 1) {
116 
117 #ifdef Libisofs_old_ecma119_nameS
118 
119             int max_len;
120 
121             if (relaxed) {
122                 if (strchr(ascii_name, '.') == NULL)
123                     max_len = 8;
124                 else
125                     max_len = 11;
126                 isoname = iso_r_fileid(ascii_name, max_len, relaxed,
127                                        force_dots);
128             } else {
129                 isoname = iso_1_fileid(ascii_name, 0, force_dots);
130             }
131 
132 #else /* Libisofs_old_ecma119_nameS */
133 
134             isoname = iso_1_fileid(ascii_name, relaxed, force_dots);
135 
136 #endif /* ! Libisofs_old_ecma119_nameS */
137 
138         } else {
139             if (relaxed || !force_dots) {
140                 isoname = iso_r_fileid(ascii_name, 30, relaxed, force_dots);
141             } else {
142                 isoname = iso_2_fileid(ascii_name);
143             }
144         }
145     }
146     if (free_ascii_name)
147         free(ascii_name);
148     if (isoname != NULL) {
149         *name = isoname;
150         return ISO_SUCCESS;
151     } else {
152         /*
153          * only possible if mem error, as check for empty names is done
154          * in public tree
155          */
156         return ISO_OUT_OF_MEM;
157     }
158 }
159 
160 static
get_iso_name(Ecma119Image * img,IsoNode * iso,char ** name)161 int get_iso_name(Ecma119Image *img, IsoNode *iso, char **name)
162 {
163     int ret;
164 
165     ret = iso_get_ecma119_name(img->opts, img->input_charset, img->image->id,
166                                iso->name, iso->type, name, 0);
167     return ret;
168 }
169 
ecma119_is_dedicated_reloc_dir(Ecma119Image * img,Ecma119Node * node)170 int ecma119_is_dedicated_reloc_dir(Ecma119Image *img, Ecma119Node *node)
171 {
172     if (img->rr_reloc_node == node &&
173         node != img->root && node != img->partition_root &&
174         (img->opts->rr_reloc_flags & 2))
175         return 1;
176     return 0;
177 }
178 
179 static
create_ecma119_node(Ecma119Image * img,IsoNode * iso,Ecma119Node ** node)180 int create_ecma119_node(Ecma119Image *img, IsoNode *iso, Ecma119Node **node)
181 {
182     Ecma119Node *ecma;
183 
184     ecma = calloc(1, sizeof(Ecma119Node));
185     if (ecma == NULL) {
186         return ISO_OUT_OF_MEM;
187     }
188 
189     ecma->node = iso;
190     iso_node_ref(iso);
191     ecma->nlink = 1;
192     *node = ecma;
193     return ISO_SUCCESS;
194 }
195 
196 /**
197  * Create a new ECMA-119 node representing a directory from a iso directory
198  * node.
199  */
200 static
create_dir(Ecma119Image * img,IsoDir * iso,Ecma119Node ** node)201 int create_dir(Ecma119Image *img, IsoDir *iso, Ecma119Node **node)
202 {
203     int ret;
204     Ecma119Node **children = NULL;
205     struct ecma119_dir_info *dir_info;
206 
207     if (iso->nchildren > 0) {
208         children = calloc(1, sizeof(void*) * iso->nchildren);
209         if (children == NULL)
210             return ISO_OUT_OF_MEM;
211     }
212 
213     dir_info = calloc(1, sizeof(struct ecma119_dir_info));
214     if (dir_info == NULL) {
215         if (children != NULL)
216             free(children);
217         return ISO_OUT_OF_MEM;
218     }
219 
220     ret = create_ecma119_node(img, (IsoNode*)iso, node);
221     if (ret < 0) {
222         if (children != NULL)
223             free(children);
224         free(dir_info);
225         return ret;
226     }
227     (*node)->type = ECMA119_DIR;
228     (*node)->info.dir = dir_info;
229     (*node)->info.dir->nchildren = 0;
230     (*node)->info.dir->children = children;
231     return ISO_SUCCESS;
232 }
233 
234 
235 static
create_file_src(Ecma119Image * img,IsoFile * iso,IsoFileSrc ** src)236 int create_file_src(Ecma119Image *img, IsoFile *iso, IsoFileSrc **src)
237 {
238     int ret;
239     off_t size;
240 
241     size = iso_stream_get_size(iso->stream);
242     if (size > (off_t)MAX_ISO_FILE_SECTION_SIZE && img->opts->iso_level != 3) {
243         char *ipath = iso_tree_get_node_path(ISO_NODE(iso));
244         iso_msg_submit(img->image->id, ISO_FILE_TOO_BIG, 0,
245                               "File \"%s\" cannot be added to image because "
246                               "its size is 4 GiB or larger", ipath);
247         free(ipath);
248         return ISO_FILE_TOO_BIG;
249     }
250     ret = iso_file_src_create(img, iso, src);
251     if (ret < 0) {
252         return ret;
253     }
254     return 0;
255 }
256 
257 
258 /**
259  * Create a new ECMA-119 node representing a regular file from a iso file
260  * node.
261  */
262 static
create_file(Ecma119Image * img,IsoFile * iso,Ecma119Node ** node)263 int create_file(Ecma119Image *img, IsoFile *iso, Ecma119Node **node)
264 {
265     int ret;
266     IsoFileSrc *src;
267 
268     ret = create_file_src(img, iso, &src);
269     if (ret < 0) {
270         return ret;
271     }
272 
273     ret = create_ecma119_node(img, (IsoNode*)iso, node);
274     if (ret < 0) {
275         /*
276          * the src doesn't need to be freed, it is free together with
277          * the Ecma119Image
278          */
279         return ret;
280     }
281     (*node)->type = ECMA119_FILE;
282     (*node)->info.file = src;
283 
284     return ret;
285 }
286 
287 /**
288  * Create a new ECMA-119 node representing a regular file from an El-Torito
289  * boot catalog
290  */
291 static
create_boot_cat(Ecma119Image * img,IsoBoot * iso,Ecma119Node ** node)292 int create_boot_cat(Ecma119Image *img, IsoBoot *iso, Ecma119Node **node)
293 {
294     int ret;
295     IsoFileSrc *src;
296 
297     ret = el_torito_catalog_file_src_create(img, &src);
298     if (ret < 0) {
299         return ret;
300     }
301 
302     ret = create_ecma119_node(img, (IsoNode*)iso, node);
303     if (ret < 0) {
304         /*
305          * the src doesn't need to be freed, it is free together with
306          * the Ecma119Image
307          */
308         return ret;
309     }
310     (*node)->type = ECMA119_FILE;
311     (*node)->info.file = src;
312 
313     return ret;
314 }
315 
316 /**
317  * Create a new ECMA-119 node representing a symbolic link from a iso symlink
318  * node.
319  */
320 static
create_symlink(Ecma119Image * img,IsoSymlink * iso,Ecma119Node ** node)321 int create_symlink(Ecma119Image *img, IsoSymlink *iso, Ecma119Node **node)
322 {
323     int ret;
324 
325     ret = create_ecma119_node(img, (IsoNode*)iso, node);
326     if (ret < 0) {
327         return ret;
328     }
329     (*node)->type = ECMA119_SYMLINK;
330     return ISO_SUCCESS;
331 }
332 
333 /**
334  * Create a new ECMA-119 node representing a special file.
335  */
336 static
create_special(Ecma119Image * img,IsoSpecial * iso,Ecma119Node ** node)337 int create_special(Ecma119Image *img, IsoSpecial *iso, Ecma119Node **node)
338 {
339     int ret;
340 
341     ret = create_ecma119_node(img, (IsoNode*)iso, node);
342     if (ret < 0) {
343         return ret;
344     }
345     (*node)->type = ECMA119_SPECIAL;
346     return ISO_SUCCESS;
347 }
348 
ecma119_node_free(Ecma119Node * node)349 void ecma119_node_free(Ecma119Node *node)
350 {
351     if (node == NULL) {
352         return;
353     }
354     if (node->type == ECMA119_DIR) {
355         size_t i;
356         for (i = 0; i < node->info.dir->nchildren; i++) {
357             ecma119_node_free(node->info.dir->children[i]);
358         }
359         if (node->info.dir->children != NULL)
360             free(node->info.dir->children);
361         free(node->info.dir);
362     }
363     free(node->iso_name);
364     iso_node_unref(node->node);
365     free(node);
366 }
367 
368 
369 static
add_to_hidden_list(Ecma119Image * image,IsoFileSrc * src)370 int add_to_hidden_list(Ecma119Image *image, IsoFileSrc *src)
371 {
372     int ret;
373     struct iso_filesrc_list_item *item;
374 
375     LIBISO_ALLOC_MEM(item, struct iso_filesrc_list_item, 1);
376     item->src = src;
377     item->next = image->ecma119_hidden_list;
378     image->ecma119_hidden_list = item;
379     ret = ISO_SUCCESS;
380 ex:
381     return ret;
382 }
383 
384 
iso_filesrc_list_destroy(struct iso_filesrc_list_item ** start_item)385 int iso_filesrc_list_destroy(struct iso_filesrc_list_item **start_item)
386 {
387     struct iso_filesrc_list_item *item, *next;
388 
389     for (item = *start_item; item != NULL; item = next) {
390         next = item->next;
391         LIBISO_FREE_MEM(item);
392     }
393     return ISO_SUCCESS;
394 }
395 
396 
397 /**
398  * @param flag
399  *      bit0= iso is in a hidden directory. Thus hide it.
400  * @return
401  *      1 success, 0 node ignored,  < 0 error
402  *
403  */
404 static
create_tree(Ecma119Image * image,IsoNode * iso,Ecma119Node ** tree,int depth,int pathlen,int flag)405 int create_tree(Ecma119Image *image, IsoNode *iso, Ecma119Node **tree,
406                 int depth, int pathlen, int flag)
407 {
408     int ret, hidden;
409     Ecma119Node *node = NULL;
410     int max_path;
411     char *iso_name= NULL, *ipath = NULL;
412     IsoFileSrc *src = NULL;
413     IsoWriteOpts *opts;
414 
415     if (image == NULL || iso == NULL || tree == NULL) {
416         return ISO_NULL_POINTER;
417     }
418     opts = image->opts;
419     *tree = NULL;
420 
421     hidden = flag & 1;
422     if (iso->hidden & LIBISO_HIDE_ON_RR) {
423         hidden = 1;
424         if (!((iso->hidden & LIBISO_HIDE_BUT_WRITE) ||
425               iso->type == LIBISO_BOOT)) {
426             return 0; /* file will be ignored */
427         }
428     }
429 
430     if (hidden) {
431         max_path= pathlen;
432     } else {
433         ret = get_iso_name(image, iso, &iso_name);
434         if (ret < 0) {
435             iso_name = NULL; /* invalid, do not free */
436             goto ex;
437         }
438         max_path = pathlen + 1 + (iso_name ? strlen(iso_name) : 0);
439         if (!opts->rockridge) {
440             if ((iso->type == LIBISO_DIR && depth > 8) &&
441                 !opts->allow_deep_paths) {
442                 ipath = iso_tree_get_node_path(iso);
443                 ret = iso_msg_submit(image->image->id, ISO_FILE_IMGPATH_WRONG,
444                                      0, "File \"%s\" can't be added, "
445                                      "because directory depth "
446                                      "is greater than 8.", ipath);
447                 goto ex;
448             } else if (max_path > 255 && !opts->allow_longer_paths) {
449                 ipath = iso_tree_get_node_path(iso);
450                 ret = iso_msg_submit(image->image->id, ISO_FILE_IMGPATH_WRONG,
451                                      0, "File \"%s\" can't be added, "
452                                      "because path length "
453                                      "is greater than 255 characters", ipath);
454                 goto ex;
455             }
456         }
457     }
458 
459     switch (iso->type) {
460     case LIBISO_FILE:
461         if (hidden) {
462             ret = create_file_src(image, (IsoFile *) iso, &src);
463             if (ret <= 0)
464                 goto ex;
465             ret = add_to_hidden_list(image, src);
466         } else {
467             ret = create_file(image, (IsoFile*)iso, &node);
468         }
469         break;
470     case LIBISO_SYMLINK:
471         if (hidden) {
472             ret = 0; /* Hidden means non-existing */
473             goto ex;
474         }
475         if (opts->rockridge) {
476             ret = create_symlink(image, (IsoSymlink*)iso, &node);
477         } else {
478             /* symlinks are only supported when RR is enabled */
479             char *ipath = iso_tree_get_node_path(iso);
480             ret = iso_msg_submit(image->image->id, ISO_FILE_IGNORED, 0,
481                 "File \"%s\" ignored. Symlinks need RockRidge extensions.",
482                 ipath);
483             free(ipath);
484         }
485         break;
486     case LIBISO_SPECIAL:
487         if (hidden) {
488             ret = 0; /* Hidden means non-existing */
489             goto ex;
490         }
491         if (opts->rockridge) {
492             ret = create_special(image, (IsoSpecial*)iso, &node);
493         } else {
494             /* special files are only supported when RR is enabled */
495             char *ipath = iso_tree_get_node_path(iso);
496             ret = iso_msg_submit(image->image->id, ISO_FILE_IGNORED, 0,
497                 "File \"%s\" ignored. Special files need RockRidge extensions.",
498                 ipath);
499             free(ipath);
500         }
501         break;
502     case LIBISO_BOOT:
503         if (image->eltorito) {
504             if (hidden) {
505                 ret = el_torito_catalog_file_src_create(image, &src);
506                 if (ret <= 0)
507                     goto ex;
508                 ret = add_to_hidden_list(image, src);
509             } else {
510                 ret = create_boot_cat(image, (IsoBoot*)iso, &node);
511             }
512         } else {
513             /* log and ignore */
514             ret = iso_msg_submit(image->image->id, ISO_FILE_IGNORED, 0,
515                 "El-Torito catalog found on a image without El-Torito.");
516         }
517         break;
518     case LIBISO_DIR:
519         {
520             IsoNode *pos;
521             IsoDir *dir = (IsoDir*)iso;
522 
523             if (!hidden) {
524                 ret = create_dir(image, dir, &node);
525                 if (ret < 0) {
526                     goto ex;
527                 }
528                 if (depth == 1) { /* root is default */
529                     image->rr_reloc_node = node;
530                 } else if (depth == 2) {
531                     /* Directories in root may be used as relocation dir */
532                     if (opts->rr_reloc_dir != NULL)
533                         if (opts->rr_reloc_dir[0] != 0 &&
534                             strcmp(iso->name, opts->rr_reloc_dir) == 0)
535                             image->rr_reloc_node = node;
536                 }
537             }
538             ret = ISO_SUCCESS;
539             pos = dir->children;
540             while (pos) {
541                 int cret;
542                 Ecma119Node *child;
543                 cret = create_tree(image, pos, &child, depth + 1, max_path,
544                                    !!hidden);
545                 if (cret < 0) {
546                     /* error */
547                     ret = cret;
548                     break;
549                 } else if (cret == ISO_SUCCESS && !hidden) {
550                     /* add child to this node */
551                     int nchildren = node->info.dir->nchildren++;
552                     node->info.dir->children[nchildren] = child;
553                     child->parent = node;
554                 }
555                 pos = pos->next;
556             }
557         }
558         break;
559     default:
560         /* should never happen */
561         ret = ISO_ASSERT_FAILURE;
562         goto ex;
563     }
564     if (ret <= 0) {
565         goto ex;
566     }
567     if (!hidden) {
568         node->iso_name = iso_name;
569         iso_name = NULL; /* now owned by node, do not free */
570         *tree = node;
571         node = NULL;     /* now owned by caller, do not free */
572     }
573     ret = ISO_SUCCESS;
574 ex:
575     if (iso_name != NULL)
576         free(iso_name);
577     if (ipath != NULL)
578         free(ipath);
579     if (node != NULL)
580         ecma119_node_free(node);
581     if (hidden && ret == ISO_SUCCESS)
582         ret = 0;
583     /* The sources of hidden files are now owned by the rb-tree */
584     return ret;
585 }
586 
587 /**
588  * Compare the iso name of two ECMA-119 nodes
589  */
590 static
cmp_node_name(const void * f1,const void * f2)591 int cmp_node_name(const void *f1, const void *f2)
592 {
593     Ecma119Node *f = *((Ecma119Node**)f1);
594     Ecma119Node *g = *((Ecma119Node**)f2);
595     return strcmp(f->iso_name, g->iso_name);
596 }
597 
598 /**
599  * Sorts a the children of each directory in the ECMA-119 tree represented
600  * by \p root, according to the order specified in ECMA-119, section 9.3.
601  */
602 static
sort_tree(Ecma119Node * root)603 void sort_tree(Ecma119Node *root)
604 {
605     size_t i;
606 
607     if (root->info.dir->children == NULL)
608         return;
609     qsort(root->info.dir->children, root->info.dir->nchildren, sizeof(void*),
610           cmp_node_name);
611     for (i = 0; i < root->info.dir->nchildren; i++) {
612         if (root->info.dir->children[i]->type == ECMA119_DIR)
613             sort_tree(root->info.dir->children[i]);
614     }
615 }
616 
617 /**
618  * Ensures that the ISO name of each children of the given dir is unique,
619  * changing some of them if needed.
620  * It also ensures that resulting filename is always <= than given
621  * max_name_len, including extension. If needed, the extension will be reduced,
622  * but never under 3 characters.
623  */
624 static
mangle_single_dir(Ecma119Image * img,Ecma119Node * dir,int max_file_len,int max_dir_len)625 int mangle_single_dir(Ecma119Image *img, Ecma119Node *dir, int max_file_len,
626                       int max_dir_len)
627 {
628     int ret;
629     int i, nchildren;
630     Ecma119Node **children;
631     IsoHTable *table;
632     int need_sort = 0;
633 
634     nchildren = dir->info.dir->nchildren;
635     children = dir->info.dir->children;
636 
637     if (nchildren <= 0)
638         return ISO_SUCCESS; /* nothing to do */
639 
640     /* a hash table will temporary hold the names, for fast searching */
641     ret = iso_htable_create((nchildren * 100) / 80, iso_str_hash,
642                             (compare_function_t)strcmp, &table);
643     if (ret < 0) {
644         return ret;
645     }
646     for (i = 0; i < nchildren; ++i) {
647         char *name = children[i]->iso_name;
648         ret = iso_htable_add(table, name, name);
649         if (ret < 0) {
650             goto mangle_cleanup;
651         }
652     }
653 
654     for (i = 0; i < nchildren; ++i) {
655         char *name, *ext;
656         char full_name[40];
657         const int full_max_len = 40 - 1;
658         int max; /* computed max len for name, without extension */
659         int j = i;
660         int digits = 1; /* characters to change per name */
661 
662         /* first, find all child with same name */
663         while (j + 1 < nchildren && !cmp_node_name(children + i, children + j
664                 + 1)) {
665             ++j;
666         }
667         if (j == i) {
668             /* name is unique */
669             continue;
670         }
671 
672         if (img->opts->untranslated_name_len) {
673             /* This should not happen because no two IsoNode names should be
674                identical and only unaltered IsoNode names should be seen here.
675                Thus the Ema119Node names should be unique.
676             */
677             iso_msg_submit(img->image->id, ISO_NAME_NEEDS_TRANSL, 0,
678                            "ECMA-119 file name collision: '%s'",
679                            children[i]->iso_name);
680             ret = ISO_NAME_NEEDS_TRANSL;
681             goto mangle_cleanup;
682         }
683 
684         /*
685          * A max of 7 characters is good enough, it allows handling up to
686          * 9,999,999 files with same name. We can increment this to
687          * max_name_len, but the int_pow() function must then be modified
688          * to return a bigger integer.
689          */
690         while (digits < 8) {
691             int ok, k;
692             char *dot;
693             int change = 0; /* number to be written */
694 
695             /* copy name to buffer */
696             strncpy(full_name, children[i]->iso_name, full_max_len);
697             full_name[full_max_len] = 0;
698 
699             /* compute name and extension */
700             dot = strrchr(full_name, '.');
701             if (dot != NULL &&
702                 (children[i]->type != ECMA119_DIR ||
703                  img->opts->allow_dir_id_ext)) {
704 
705                 /*
706                  * File (normally not dir) with extension
707                  * Note that we don't need to check for placeholders, as
708                  * tree reparent happens later, so no placeholders can be
709                  * here at this time.
710                  */
711                 int extlen;
712                 full_name[dot - full_name] = '\0';
713                 name = full_name;
714                 ext = dot + 1;
715 
716                 /*
717                  * For iso level 1 we force ext len to be 3, as name
718                  * can't grow on the extension space
719                  */
720                 extlen = (max_file_len == 12) ? 3 : strlen(ext);
721                 max = max_file_len - extlen - 1 - digits;
722                 if (max <= 0) {
723                     /* this can happen if extension is too long */
724                     if (extlen + max > 3) {
725                         /*
726                          * reduce extension len, to give name an extra char
727                          * note that max is negative or 0
728                          */
729                         extlen = extlen + max - 1;
730                         ext[extlen] = '\0';
731                         max = max_file_len - extlen - 1 - digits;
732                     } else {
733                         /*
734                          * error, we don't support extensions < 3
735                          * This can't happen with current limit of digits.
736                          */
737                         ret = ISO_ERROR;
738                         goto mangle_cleanup;
739                     }
740                 }
741                 /* ok, reduce name by digits */
742                 if (name + max < dot) {
743                     name[max] = '\0';
744                 }
745             } else {
746                 /* Directory (normally), or file without extension */
747                 if (children[i]->type == ECMA119_DIR) {
748                     max = max_dir_len - digits;
749                     dot = NULL; /* dots (normally) have no meaning in dirs */
750                 } else {
751                     max = max_file_len - digits;
752                 }
753                 name = full_name;
754                 if ((size_t) max < strlen(name)) {
755                     name[max] = '\0';
756                 }
757                 /* let ext be an empty string */
758                 ext = name + strlen(name);
759             }
760 
761             ok = 1;
762             /* change name of each file */
763             for (k = i; k <= j; ++k) {
764                 char tmp[40];
765                 char fmt[16];
766                 if (dot != NULL) {
767                     sprintf(fmt, "%%s%%0%dd.%%s", digits);
768                 } else {
769                     sprintf(fmt, "%%s%%0%dd%%s", digits);
770                 }
771                 while (1) {
772                     sprintf(tmp, fmt, name, change, ext);
773                     ++change;
774                     if (change > int_pow(10, digits)) {
775                         ok = 0;
776                         break;
777                     }
778                     if (!iso_htable_get(table, tmp, NULL)) {
779                         /* the name is unique, so it can be used */
780                         break;
781                     }
782                 }
783                 if (ok) {
784                     char *new = strdup(tmp);
785                     if (new == NULL) {
786                         ret = ISO_OUT_OF_MEM;
787                         goto mangle_cleanup;
788                     }
789 
790 #ifdef Libisofs_extra_verbose_debuG
791                     iso_msg_debug(img->image->id, "\"%s\" renamed to \"%s\"",
792                                   children[k]->iso_name, new);
793 #endif
794 
795                     iso_htable_remove_ptr(table, children[k]->iso_name, NULL);
796                     free(children[k]->iso_name);
797                     children[k]->iso_name = new;
798                     iso_htable_add(table, new, new);
799 
800                     /*
801                      * if we change a name we need to sort again children
802                      * at the end
803                      */
804                     need_sort = 1;
805                 } else {
806                     /* we need to increment digits */
807                     break;
808                 }
809             }
810             if (ok) {
811                 break;
812             } else {
813                 ++digits;
814             }
815         }
816         if (digits == 8) {
817             ret = ISO_MANGLE_TOO_MUCH_FILES;
818             goto mangle_cleanup;
819         }
820         i = j;
821     }
822 
823     /*
824      * If needed, sort again the files inside dir
825      */
826     if (need_sort) {
827         qsort(children, nchildren, sizeof(void*), cmp_node_name);
828     }
829 
830     ret = ISO_SUCCESS;
831 
832 mangle_cleanup : ;
833     iso_htable_destroy(table, NULL);
834     return ret;
835 }
836 
837 static
mangle_dir(Ecma119Image * img,Ecma119Node * dir,int max_file_len,int max_dir_len)838 int mangle_dir(Ecma119Image *img, Ecma119Node *dir, int max_file_len,
839                int max_dir_len)
840 {
841     int ret;
842     size_t i;
843 
844     ret = mangle_single_dir(img, dir, max_file_len, max_dir_len);
845     if (ret < 0) {
846         return ret;
847     }
848 
849     /* recurse */
850     for (i = 0; i < dir->info.dir->nchildren; ++i) {
851         if (dir->info.dir->children[i]->type == ECMA119_DIR) {
852             ret = mangle_dir(img, dir->info.dir->children[i], max_file_len,
853                              max_dir_len);
854             if (ret < 0) {
855                 /* error */
856                 return ret;
857             }
858         }
859     }
860     return ISO_SUCCESS;
861 }
862 
863 static
mangle_tree(Ecma119Image * img,Ecma119Node * dir,int recurse)864 int mangle_tree(Ecma119Image *img, Ecma119Node *dir, int recurse)
865 {
866     int max_file, max_dir;
867     Ecma119Node *root;
868 
869     if (img->opts->untranslated_name_len > 0) {
870         max_file = max_dir = img->opts->untranslated_name_len;
871     } else if (img->opts->max_37_char_filenames) {
872         max_file = max_dir = 37;
873     } else if (img->opts->iso_level == 1) {
874         max_file = 12; /* 8 + 3 + 1 */
875         max_dir = 8;
876     } else {
877         max_file = max_dir = 31;
878     }
879     if (dir != NULL) {
880         root = dir;
881     } else if (img->eff_partition_offset > 0) {
882         root = img->partition_root;
883     } else {
884         root = img->root;
885     }
886     if (recurse) {
887         return mangle_dir(img, root, max_file, max_dir);
888     } else {
889         return mangle_single_dir(img, root, max_file, max_dir);
890     }
891 }
892 
893 /**
894  * Create a new ECMA-119 node representing a placeholder for a relocated
895  * dir.
896  *
897  * See IEEE P1282, section 4.1.5 for details
898  */
899 static
create_placeholder(Ecma119Node * parent,Ecma119Node * real,Ecma119Node ** node)900 int create_placeholder(Ecma119Node *parent, Ecma119Node *real,
901                        Ecma119Node **node)
902 {
903     Ecma119Node *ret;
904 
905     ret = calloc(1, sizeof(Ecma119Node));
906     if (ret == NULL) {
907         return ISO_OUT_OF_MEM;
908     }
909 
910     /*
911      * TODO
912      * If real is a dir, while placeholder is a file, ISO name restricctions
913      * are different, what to do?
914      */
915     ret->iso_name = strdup(real->iso_name);
916     if (ret->iso_name == NULL) {
917         free(ret);
918         return ISO_OUT_OF_MEM;
919     }
920 
921     /* take a ref to the IsoNode */
922     ret->node = real->node;
923     iso_node_ref(real->node);
924     ret->parent = parent;
925     ret->type = ECMA119_PLACEHOLDER;
926     ret->info.real_me = real;
927     ret->ino = real->ino;
928     ret->nlink = real->nlink;
929 
930     *node = ret;
931     return ISO_SUCCESS;
932 }
933 
934 static
max_child_name_len(Ecma119Node * dir)935 size_t max_child_name_len(Ecma119Node *dir)
936 {
937     size_t ret = 0, i;
938     for (i = 0; i < dir->info.dir->nchildren; i++) {
939         size_t len = strlen(dir->info.dir->children[i]->iso_name);
940         ret = MAX(ret, len);
941     }
942     return ret;
943 }
944 
945 /**
946  * Relocates a directory, as specified in Rock Ridge Specification
947  * (see IEEE P1282, section 4.1.5). This is needed when the number of levels
948  * on a directory hierarchy exceeds 8, or the length of a path is higher
949  * than 255 characters, as specified in ECMA-119, section 6.8.2.1
950  */
951 static
reparent(Ecma119Node * child,Ecma119Node * parent)952 int reparent(Ecma119Node *child, Ecma119Node *parent)
953 {
954     int ret;
955     size_t i;
956     Ecma119Node *placeholder;
957 
958     /* replace the child in the original parent with a placeholder */
959     for (i = 0; i < child->parent->info.dir->nchildren; i++) {
960         if (child->parent->info.dir->children[i] == child) {
961             ret = create_placeholder(child->parent, child, &placeholder);
962             if (ret < 0) {
963                 return ret;
964             }
965             child->parent->info.dir->children[i] = placeholder;
966             break;
967         }
968     }
969 
970     /* just for debug, this should never happen... */
971     if (i == child->parent->info.dir->nchildren) {
972         return ISO_ASSERT_FAILURE;
973     }
974 
975     /* keep track of the real parent */
976     child->info.dir->real_parent = child->parent;
977 
978     /* add the child to its new parent */
979     child->parent = parent;
980     parent->info.dir->nchildren++;
981     parent->info.dir->children = realloc(parent->info.dir->children,
982                                  sizeof(void*) * parent->info.dir->nchildren);
983     parent->info.dir->children[parent->info.dir->nchildren - 1] = child;
984     return ISO_SUCCESS;
985 }
986 
987 /**
988  * Reorder the tree, if necessary, to ensure that
989  *  - the depth is at most 8
990  *  - each path length is at most 255 characters
991  * This restriction is imposed by ECMA-119 specification (ECMA-119, 6.8.2.1).
992  *
993  * @param dir
994  *      Dir we are currently processing
995  * @param level
996  *      Level of the directory in the hierarchy
997  * @param pathlen
998  *      Length of the path until dir, including it
999  * @return
1000  *      1 success, < 0 error
1001  */
1002 static
reorder_tree(Ecma119Image * img,Ecma119Node * dir,int dir_level,int dir_pathlen)1003 int reorder_tree(Ecma119Image *img, Ecma119Node *dir,
1004                  int dir_level, int dir_pathlen)
1005 {
1006     int ret, level, pathlen, newpathlen;
1007     size_t max_path, i;
1008     Ecma119Node *reloc, *child;
1009 
1010     /* might change by relocation */
1011     level = dir_level;
1012     pathlen = dir_pathlen;
1013 
1014     max_path = pathlen + 1 + max_child_name_len(dir);
1015 
1016     if (level > 8 || max_path > 255) {
1017         reloc = img->rr_reloc_node;
1018         if (reloc == NULL) {
1019             if (img->eff_partition_offset > 0) {
1020                 reloc = img->partition_root;
1021             } else {
1022                 reloc = img->root;
1023             }
1024         }
1025         ret = reparent(dir, reloc);
1026         if (ret < 0) {
1027             return ret;
1028         }
1029 
1030         if (reloc == img->root || reloc == img->partition_root) {
1031             /*
1032              * we are appended to the root's children now, so there is no
1033              * need to recurse (the root will hit us again)
1034              */
1035             return ISO_SUCCESS;
1036         }
1037 
1038         /* dir is now the relocated Ecma119Node */
1039         pathlen = 37 + 1; /* The dir name might get longer by mangling */
1040         level = 2;
1041         if (img->opts->rr_reloc_dir != NULL) {
1042             pathlen += strlen(img->rr_reloc_node->iso_name) + 1;
1043             if(img->opts->rr_reloc_dir[0] != 0)
1044               level = 3;
1045         }
1046     }
1047 
1048     if (ecma119_is_dedicated_reloc_dir(img, (Ecma119Node *) dir))
1049         return ISO_SUCCESS;
1050 
1051     for (i = 0; i < dir->info.dir->nchildren; i++) {
1052         child = dir->info.dir->children[i];
1053         if (child->type == ECMA119_DIR) {
1054             newpathlen = pathlen + 1 + strlen(child->iso_name);
1055             ret = reorder_tree(img, child, level + 1, newpathlen);
1056             if (ret < 0)
1057                 return ret;
1058         }
1059     }
1060     return ISO_SUCCESS;
1061 }
1062 
1063 /*
1064  * @param flag
1065  *     bit0= recursion
1066  *     bit1= count nodes rather than fill them into *nodes
1067  * @return
1068  *     <0 error
1069  *     bit0= saw ino == 0
1070  *     bit1= saw ino != 0
1071  */
1072 static
make_node_array(Ecma119Image * img,Ecma119Node * dir,Ecma119Node ** nodes,size_t nodes_size,size_t * node_count,int flag)1073 int make_node_array(Ecma119Image *img, Ecma119Node *dir,
1074                     Ecma119Node **nodes, size_t nodes_size, size_t *node_count,
1075                     int flag)
1076 {
1077     int ret, result = 0;
1078     size_t i;
1079     Ecma119Node *child;
1080 
1081     if (!(flag & 1)) {
1082         *node_count = 0;
1083         if (!(flag & 2)) {
1084             /* Register the tree root node */
1085             if (*node_count >= nodes_size) {
1086                 iso_msg_submit(img->image->id, ISO_ASSERT_FAILURE, 0,
1087                          "Programming error: Overflow of hardlink sort array");
1088                 return ISO_ASSERT_FAILURE;
1089             }
1090             nodes[*node_count] = dir;
1091         }
1092         result|= (dir->ino == 0 ? 1 : 2);
1093         (*node_count)++;
1094     }
1095 
1096     for (i = 0; i < dir->info.dir->nchildren; i++) {
1097         child = dir->info.dir->children[i];
1098         if (!(flag & 2)) {
1099             if (*node_count >= nodes_size) {
1100                 iso_msg_submit(img->image->id, ISO_ASSERT_FAILURE, 0,
1101                          "Programming error: Overflow of hardlink sort array");
1102                 return ISO_ASSERT_FAILURE;
1103             }
1104             nodes[*node_count] = child;
1105         }
1106         result|= (child->ino == 0 ? 1 : 2);
1107         (*node_count)++;
1108 
1109         if (child->type == ECMA119_DIR) {
1110             ret = make_node_array(img, child,
1111                                   nodes, nodes_size, node_count, flag | 1);
1112             if (ret < 0)
1113                 return ret;
1114         }
1115     }
1116     return result;
1117 }
1118 
1119 /*
1120  * @param flag
1121  *     bit0= compare stat properties and attributes
1122  *     bit1= treat all nodes with image ino == 0 as unique
1123  */
1124 static
ecma119_node_cmp_flag(const void * v1,const void * v2,int flag)1125 int ecma119_node_cmp_flag(const void *v1, const void *v2, int flag)
1126 {
1127     int ret;
1128     Ecma119Node *n1, *n2;
1129 
1130     n1 = *((Ecma119Node **) v1);
1131     n2 = *((Ecma119Node **) v2);
1132     if (n1 == n2)
1133         return 0;
1134 
1135     ret = iso_node_cmp_flag(n1->node, n2->node, flag & (1 | 2));
1136     return ret;
1137 }
1138 
1139 static
ecma119_node_cmp_hard(const void * v1,const void * v2)1140 int ecma119_node_cmp_hard(const void *v1, const void *v2)
1141 {
1142     return ecma119_node_cmp_flag(v1, v2, 1);
1143 }
1144 
1145 static
ecma119_node_cmp_nohard(const void * v1,const void * v2)1146 int ecma119_node_cmp_nohard(const void *v1, const void *v2)
1147 {
1148     return ecma119_node_cmp_flag(v1, v2, 1 | 2);
1149 }
1150 
1151 static
family_set_ino(Ecma119Image * img,Ecma119Node ** nodes,size_t family_start,size_t next_family,ino_t img_ino,ino_t prev_ino,int flag)1152 int family_set_ino(Ecma119Image *img, Ecma119Node **nodes, size_t family_start,
1153                    size_t next_family, ino_t img_ino, ino_t prev_ino, int flag)
1154 {
1155     size_t i;
1156 
1157     if (img_ino != 0) {
1158         /* Check whether this is the same img_ino as in the previous
1159            family (e.g. by property divergence of imported hardlink).
1160         */
1161         if (img_ino == prev_ino)
1162             img_ino = 0;
1163 
1164 	/* Accept only if it is within the 32 bit range. */
1165         if (((uint64_t) img_ino) > 0xffffffff)
1166             img_ino = 0;
1167 
1168     }
1169     if (img_ino == 0) {
1170         img_ino = img_give_ino_number(img->image, 0);
1171     }
1172     for (i = family_start; i < next_family; i++) {
1173         nodes[i]->ino = img_ino;
1174         nodes[i]->nlink = next_family - family_start;
1175     }
1176     return 1;
1177 }
1178 
1179 static
match_hardlinks(Ecma119Image * img,Ecma119Node * dir,int flag)1180 int match_hardlinks(Ecma119Image *img, Ecma119Node *dir, int flag)
1181 {
1182     int ret;
1183     size_t nodes_size = 0, node_count = 0, i, family_start;
1184     Ecma119Node **nodes = NULL;
1185     unsigned int fs_id;
1186     dev_t dev_id;
1187     ino_t img_ino = 0, prev_ino = 0;
1188 
1189     ret = make_node_array(img, dir, nodes, nodes_size, &node_count, 2);
1190     if (ret < 0)
1191         return ret;
1192     nodes_size = node_count;
1193     nodes = (Ecma119Node **) calloc(sizeof(Ecma119Node *), nodes_size);
1194     if (nodes == NULL)
1195         return ISO_OUT_OF_MEM;
1196     ret = make_node_array(img, dir, nodes, nodes_size, &node_count, 0);
1197     if (ret < 0)
1198         goto ex;
1199 
1200     /* Sort according to id tuples, IsoFileSrc identity, properties, xattr. */
1201     if (img->opts->hardlinks)
1202         qsort(nodes, node_count, sizeof(Ecma119Node *), ecma119_node_cmp_hard);
1203     else
1204         qsort(nodes, node_count, sizeof(Ecma119Node *),
1205               ecma119_node_cmp_nohard);
1206 
1207     /* Hand out image inode numbers to all Ecma119Node.ino == 0 .
1208        Same sorting rank gets same inode number.
1209        Split those image inode number families where the sort criterion
1210        differs.
1211     */
1212     iso_node_get_id(nodes[0]->node, &fs_id, &dev_id, &img_ino, 1);
1213     family_start = 0;
1214     for (i = 1; i < node_count; i++) {
1215         if (nodes[i]->type != ECMA119_DIR &&
1216             ecma119_node_cmp_hard(nodes + (i - 1), nodes + i) == 0) {
1217             /* Still in same ino family */
1218             if (img_ino == 0) { /* Just in case any member knows its img_ino */
1219                 iso_node_get_id(nodes[0]->node, &fs_id, &dev_id, &img_ino, 1);
1220             }
1221     continue;
1222         }
1223         family_set_ino(img, nodes, family_start, i, img_ino, prev_ino, 0);
1224         prev_ino = img_ino;
1225         iso_node_get_id(nodes[i]->node, &fs_id, &dev_id, &img_ino, 1);
1226         family_start = i;
1227     }
1228     family_set_ino(img, nodes, family_start, i, img_ino, prev_ino, 0);
1229 
1230     ret = ISO_SUCCESS;
1231 ex:;
1232     if (nodes != NULL)
1233         free((char *) nodes);
1234     return ret;
1235 }
1236 
ecma119_tree_create(Ecma119Image * img)1237 int ecma119_tree_create(Ecma119Image *img)
1238 {
1239     int ret;
1240     Ecma119Node *root;
1241 
1242     ret = create_tree(img, (IsoNode*)img->image->root, &root, 1, 0, 0);
1243     if (ret <= 0) {
1244         if (ret == 0) {
1245             /* unexpected error, root ignored!! This can't happen */
1246             ret = ISO_ASSERT_FAILURE;
1247         }
1248         return ret;
1249     }
1250     if (img->eff_partition_offset > 0) {
1251         img->partition_root = root;
1252     } else {
1253         img->root = root;
1254     }
1255 
1256     iso_msg_debug(img->image->id, "Matching hardlinks...");
1257     ret = match_hardlinks(img, root, 0);
1258     if (ret < 0) {
1259         return ret;
1260     }
1261 
1262     iso_msg_debug(img->image->id, "Sorting the low level tree...");
1263     sort_tree(root);
1264 
1265     iso_msg_debug(img->image->id, "Mangling names...");
1266     ret = mangle_tree(img, NULL, 1);
1267     if (ret < 0) {
1268         return ret;
1269     }
1270 
1271     if (img->opts->rockridge && !img->opts->allow_deep_paths) {
1272 
1273         /* Relocate deep directories, according to RRIP, 4.1.5 */
1274         ret = reorder_tree(img, root, 1, 0);
1275         if (ret < 0) {
1276             return ret;
1277         }
1278 
1279         /*
1280          * and we need to remangle the root directory, as the function
1281          * above could insert new directories into the relocation directory.
1282          * Note that recurse = 0, as we don't need to recurse.
1283          */
1284         ret = mangle_tree(img, img->rr_reloc_node, 0);
1285         if (ret < 0) {
1286             return ret;
1287         }
1288     }
1289 
1290     return ISO_SUCCESS;
1291 }
1292 
1293 /**
1294  * Search the tree for a certain IsoNode and return its owning Ecma119Node
1295  * or NULL.
1296  */
1297 static
search_iso_node(Ecma119Node * root,IsoNode * node)1298 Ecma119Node *search_iso_node(Ecma119Node *root, IsoNode *node)
1299 {
1300     size_t i;
1301     Ecma119Node *res = NULL;
1302 
1303     if (root->node == node)
1304         return root;
1305     for (i = 0; i < root->info.dir->nchildren && res == NULL; i++) {
1306         if (root->info.dir->children[i]->type == ECMA119_DIR)
1307             res = search_iso_node(root->info.dir->children[i], node);
1308         else if (root->info.dir->children[i]->node == node)
1309             res = root->info.dir->children[i];
1310     }
1311     return res;
1312 }
1313 
1314 
ecma119_search_iso_node(Ecma119Image * img,IsoNode * node)1315 Ecma119Node *ecma119_search_iso_node(Ecma119Image *img, IsoNode *node)
1316 {
1317     Ecma119Node *res = NULL;
1318 
1319     if (img->root != NULL)
1320         res = search_iso_node(img->root, node);
1321     return res;
1322 }
1323 
1324