~registry/kmod/master

« back to all changes in this revision

Viewing changes to libkmod/libkmod-index.c

  • Committer: Lucas De Marchi
  • Date: 2011-12-12 12:30:01 UTC
  • mfrom: (161.1.30)
  • Revision ID: git-v1:2fee2f13ce5f6b17dd672389de422217c56105e2
Merge branch 'use-mmap'

Conflicts:
        libkmod/libkmod.c

Show diffs side-by-side

added added

removed removed

Lines of Context:
32
32
 
33
33
/* index.c: module index file shared functions for modprobe and depmod */
34
34
 
 
35
#define INDEX_CHILDMAX 128
 
36
 
 
37
/* Disk format:
 
38
 
 
39
   uint32_t magic = INDEX_MAGIC;
 
40
   uint32_t version = INDEX_VERSION;
 
41
   uint32_t root_offset;
 
42
 
 
43
   (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
 
44
 
 
45
        char[] prefix; // nul terminated
 
46
 
 
47
        char first;
 
48
        char last;
 
49
        uint32_t children[last - first + 1];
 
50
 
 
51
        uint32_t value_count;
 
52
        struct {
 
53
            uint32_t priority;
 
54
            char[] value; // nul terminated
 
55
        } values[value_count];
 
56
 
 
57
   (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
 
58
   Empty prefixes are omitted, leaf nodes omit the three child-related fields.
 
59
 
 
60
   This could be optimised further by adding a sparse child format
 
61
   (indicated using a new flag).
 
62
 */
 
63
 
 
64
/* Format of node offsets within index file */
 
65
enum node_offset {
 
66
        INDEX_NODE_FLAGS    = 0xF0000000, /* Flags in high nibble */
 
67
        INDEX_NODE_PREFIX   = 0x80000000,
 
68
        INDEX_NODE_VALUES = 0x40000000,
 
69
        INDEX_NODE_CHILDS   = 0x20000000,
 
70
 
 
71
        INDEX_NODE_MASK     = 0x0FFFFFFF, /* Offset value */
 
72
};
 
73
 
35
74
void index_values_free(struct index_value *values)
36
75
{
37
76
        while (values) {
444
483
        if (node->values) {
445
484
                if (fnmatch(buf_str(buf), subkey, 0) == 0)
446
485
                        index_searchwild__allvalues(node, out);
 
486
                else
 
487
                        index_close(node);
447
488
        } else {
448
489
                index_close(node);
449
490
        }
534
575
#include <sys/stat.h>
535
576
#include <unistd.h>
536
577
 
 
578
static const char _idx_empty_str[] = "";
 
579
 
537
580
/**************************************************************************/
538
581
/*
539
582
 * Alternative implementation, using mmap to map all the file to memory when
546
589
        size_t size;
547
590
};
548
591
 
 
592
struct index_mm_value {
 
593
        unsigned int priority;
 
594
        unsigned int len;
 
595
        const char *value;
 
596
};
 
597
 
 
598
struct index_mm_value_array {
 
599
        struct index_mm_value *values;
 
600
        unsigned int len;
 
601
};
 
602
 
549
603
struct index_mm_node {
550
604
        struct index_mm *idx;
551
 
        char *prefix;
552
 
        struct index_value *values;
 
605
        const char *prefix; /* mmape'd value */
 
606
        struct index_mm_value_array values;
553
607
        unsigned char first;
554
608
        unsigned char last;
555
609
        uint32_t children[];
557
611
 
558
612
static inline uint32_t read_long_mm(void **p)
559
613
{
560
 
        uint32_t v = **((uint32_t **)p);
561
 
 
562
 
        *p = *((uint8_t **)p) + sizeof(uint32_t);
563
 
 
 
614
        uint8_t *addr = *(uint8_t **)p;
 
615
        uint32_t v;
 
616
 
 
617
        /* addr may be unalined to uint32_t */
 
618
        memcpy(&v, addr, sizeof(uint32_t));
 
619
 
 
620
        *p = addr + sizeof(uint32_t);
564
621
        return ntohl(v);
565
622
}
566
623
 
567
624
static inline uint8_t read_char_mm(void **p)
568
625
{
569
 
        uint8_t *v = *((uint8_t **)p);
570
 
        *p = v + 1;
571
 
        return *v;
572
 
}
573
 
 
574
 
static inline char *read_alloc_chars_mm(void **p)
575
 
{
576
 
        char *s = *((char **)p);
577
 
        size_t len = strlen(s) + 1;
578
 
        *p = ((char *)p) + len;
579
 
 
580
 
        return memdup(s, len);
 
626
        uint8_t *addr = *(uint8_t **)p;
 
627
        uint8_t v = *addr;
 
628
        *p = addr + sizeof(uint8_t);
 
629
        return v;
581
630
}
582
631
 
583
632
static inline char *read_chars_mm(void **p, unsigned *rlen)
584
633
{
585
 
        char *s = *((char **)p);
586
 
        size_t len = *rlen = strlen(s);
587
 
        *p = ((char *)p) + len + 1;
588
 
 
589
 
        return s;
 
634
        char *addr = *(char **)p;
 
635
        size_t len = *rlen = strlen(addr);
 
636
        *p = addr + len + 1;
 
637
        return addr;
590
638
}
591
639
 
592
640
static struct index_mm_node *index_mm_read_node(struct index_mm *idx,
593
641
                                                        uint32_t offset) {
594
642
        void *p = idx->mm;
595
643
        struct index_mm_node *node;
596
 
        char *prefix;
597
 
        int i, child_count = 0;
598
 
 
 
644
        const char *prefix;
 
645
        int i, child_count, value_count, children_padding;
 
646
        uint32_t children[INDEX_CHILDMAX];
 
647
        char first, last;
599
648
 
600
649
        if ((offset & INDEX_NODE_MASK) == 0)
601
650
                return NULL;
602
651
 
603
652
        p = (char *)p + (offset & INDEX_NODE_MASK);
604
653
 
605
 
        if (offset & INDEX_NODE_PREFIX)
606
 
                prefix = read_alloc_chars_mm(&p);
607
 
        else
608
 
                prefix = strdup("");
 
654
        if (offset & INDEX_NODE_PREFIX) {
 
655
                unsigned len;
 
656
                prefix = read_chars_mm(&p, &len);
 
657
        } else
 
658
                prefix = _idx_empty_str;
609
659
 
610
660
        if (offset & INDEX_NODE_CHILDS) {
611
 
                char first = read_char_mm(&p);
612
 
                char last = read_char_mm(&p);
 
661
                first = read_char_mm(&p);
 
662
                last = read_char_mm(&p);
613
663
                child_count = last - first + 1;
614
 
 
615
 
                node = malloc(sizeof(*node) + sizeof(uint32_t) * child_count);
616
 
 
617
 
                node->first = first;
618
 
                node->last = last;
619
 
 
620
664
                for (i = 0; i < child_count; i++)
621
 
                        node->children[i] = read_long_mm(&p);
 
665
                        children[i] = read_long_mm(&p);
622
666
        } else {
623
 
                node = malloc(sizeof(*node));
624
 
                node->first = INDEX_CHILDMAX;
625
 
                node->last = 0;
626
 
        }
627
 
 
628
 
        node->values = NULL;
629
 
 
630
 
        if (offset & INDEX_NODE_VALUES) {
631
 
                uint32_t j;
632
 
 
633
 
                for (j = read_long_mm(&p); j > 0; j--) {
634
 
                        unsigned int priority;
635
 
                        const char *value;
636
 
                        unsigned len;
637
 
 
638
 
                        priority = read_long_mm(&p);
639
 
                        value = read_chars_mm(&p, &len);
640
 
                        add_value(&node->values, value, len, priority);
641
 
                }
642
 
        }
643
 
 
644
 
        node->prefix = prefix;
 
667
                first = INDEX_CHILDMAX;
 
668
                last = 0;
 
669
                child_count = 0;
 
670
        }
 
671
 
 
672
        children_padding = (offsetof(struct index_mm_node, children) +
 
673
                            (sizeof(uint32_t) * child_count)) % sizeof(void *);
 
674
 
 
675
        if (offset & INDEX_NODE_VALUES)
 
676
                value_count = read_long_mm(&p);
 
677
        else
 
678
                value_count = 0;
 
679
 
 
680
        node = malloc(sizeof(struct index_mm_node)
 
681
                      + sizeof(uint32_t) * child_count + children_padding
 
682
                      + sizeof(struct index_mm_value) * value_count);
 
683
        if (node == NULL)
 
684
                return NULL;
 
685
 
645
686
        node->idx = idx;
 
687
        node->prefix = prefix;
 
688
        if (value_count == 0)
 
689
                node->values.values = NULL;
 
690
        else {
 
691
                node->values.values = (struct index_mm_value *)
 
692
                        ((char *)node + sizeof(struct index_mm_node) +
 
693
                         sizeof(uint32_t) * child_count + children_padding);
 
694
        }
 
695
        node->values.len = value_count;
 
696
        node->first = first;
 
697
        node->last = last;
 
698
        memcpy(node->children, children, sizeof(uint32_t) * child_count);
 
699
 
 
700
        for (i = 0; i < value_count; i++) {
 
701
                struct index_mm_value *v = node->values.values + i;
 
702
                v->priority = read_long_mm(&p);
 
703
                v->value = read_chars_mm(&p, &v->len);
 
704
        }
646
705
 
647
706
        return node;
648
707
}
649
708
 
650
709
static void index_mm_free_node(struct index_mm_node *node)
651
710
{
652
 
        free(node->prefix);
653
 
        index_values_free(node->values);
654
711
        free(node);
655
712
}
656
713
 
657
 
struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename)
 
714
struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename,
 
715
                                                                bool populate)
658
716
{
659
717
        int fd;
 
718
        int flags;
660
719
        struct stat st;
661
720
        struct index_mm *idx;
662
721
        struct {
681
740
                goto fail;
682
741
        }
683
742
 
684
 
        if ((idx->mm = mmap(0, st.st_size, PROT_READ,
685
 
                                MAP_PRIVATE | MAP_POPULATE,
686
 
                                fd, 0)) == MAP_FAILED) {
 
743
        flags = MAP_PRIVATE;
 
744
        if (populate)
 
745
                flags |= MAP_POPULATE;
 
746
 
 
747
        if ((idx->mm = mmap(0, st.st_size, PROT_READ, flags, fd, 0))
 
748
                                                        == MAP_FAILED) {
687
749
                ERR(ctx, "%m\n");
688
750
                goto fail;
689
751
        }
763
825
                i += j;
764
826
 
765
827
                if (key[i] == '\0') {
766
 
                        if (node->values) {
767
 
                                value = strdup(node->values[0].value);
 
828
                        if (node->values.len > 0) {
 
829
                                value = strdup(node->values.values[0].value);
768
830
                                index_mm_free_node(node);
769
831
                                return value;
770
832
                        } else {
803
865
static void index_mm_searchwild_allvalues(struct index_mm_node *node,
804
866
                                                struct index_value **out)
805
867
{
806
 
        struct index_value *v;
 
868
        struct index_mm_value *itr, *itr_end;
807
869
 
808
 
        for (v = node->values; v != NULL; v = v->next)
809
 
                add_value(out, v->value, v->len, v->priority);
 
870
        itr = node->values.values;
 
871
        itr_end = itr + node->values.len;
 
872
        for (; itr < itr_end; itr++)
 
873
                add_value(out, itr->value, itr->len, itr->priority);
810
874
 
811
875
        index_mm_free_node(node);
812
876
}
842
906
                buf_popchar(buf);
843
907
        }
844
908
 
845
 
        if (node->values) {
 
909
        if (node->values.len > 0) {
846
910
                if (fnmatch(buf_str(buf), subkey, 0) == 0)
847
911
                        index_mm_searchwild_allvalues(node, out);
 
912
                else
 
913
                        index_mm_free_node(node);
848
914
        } else {
849
915
                index_mm_free_node(node);
850
916
        }