How does the Linux kernel determine the order of _

There are many instances of __init calls in kernel both in drivers module_init and other functions of kernel. My doubt is how exactly kernel determines the sequence of the __init call. More importantly, How it also determine the sequence of driver module_init call?

All the init magic are implemented in files:

include/asm-generic/vmlinux.lds.h
include/linux/init.h
init/main.c

Firstly, look at include/asm-generic/vmlinux.lds.h that contains the following:

 13  *      . = START;
 14  *      __init_begin = .;
 15  *      HEAD_TEXT_SECTION
 16  *      INIT_TEXT_SECTION(PAGE_SIZE)
 17  *      INIT_DATA_SECTION(...)
 18  *      PERCPU_SECTION(CACHELINE_SIZE)
 19  *      __init_end = .;

Where INIT_TEXT_SECTION and INIT_DATA_SECTION defined as follow:

790 #define INIT_TEXT_SECTION(inittext_align)                               \
791         . = ALIGN(inittext_align);                                      \
792         .init.text : AT(ADDR(.init.text) - LOAD_OFFSET) {               \
793                 VMLINUX_SYMBOL(_sinittext) = .;                         \
794                 INIT_TEXT                                               \
795                 VMLINUX_SYMBOL(_einittext) = .;                         \
796         }
797 
798 #define INIT_DATA_SECTION(initsetup_align)                              \
799         .init.data : AT(ADDR(.init.data) - LOAD_OFFSET) {               \
800                 INIT_DATA                                               \
801                 INIT_SETUP(initsetup_align)                             \
802                 INIT_CALLS                                              \
803                 CON_INITCALL                                            \
804                 SECURITY_INITCALL                                       \
805                 INIT_RAM_FS                                             \
806         }

Let's look at INIT_CALLS defines for example:

628 #define INIT_CALLS_LEVEL(level)                                         \
629                 VMLINUX_SYMBOL(__initcall##level##_start) = .;          \
630                 *(.initcall##level##.init)                              \
631                 *(.initcall##level##s.init)  

633 #define INIT_CALLS                                                      \
634                 VMLINUX_SYMBOL(__initcall_start) = .;                   \
635                 *(.initcallearly.init)                                  \
636                 INIT_CALLS_LEVEL(0)                                     \
637                 INIT_CALLS_LEVEL(1)                                     \
638                 INIT_CALLS_LEVEL(2)                                     \
639                 INIT_CALLS_LEVEL(3)                                     \
640                 INIT_CALLS_LEVEL(4)                                     \
641                 INIT_CALLS_LEVEL(5)                                     \
642                 INIT_CALLS_LEVEL(rootfs)                                \
643                 INIT_CALLS_LEVEL(6)                                     \
644                 INIT_CALLS_LEVEL(7)                                     \
645                 VMLINUX_SYMBOL(__initcall_end) = .;

You can see the this defines the sections names that marked with.initcall.... And all the marked data gets into the __initcall_start .. __initcall_end range.

Now let's look at the [include/linux/init.h that contains the following:

44 #define __init          __section(.init.text) __cold notrace
45 #define __initdata      __section(.init.data)

And further:

189 #define __define_initcall(level,fn,id) \
190         static initcall_t __initcall_##fn##id __used \
191         __attribute__((__section__(".initcall" level ".init"))) = fn
...
220 #define device_initcall(fn) __define_initcall("6",fn,6)
...
225 #define __initcall(fn) device_initcall(fn)
...
271 /**
272  * module_init() - driver initialization entry point
273  * @x: function to be run at kernel boot time or module insertion
274  * 
275  * module_init() will either be called during do_initcalls() (if
276  * builtin) or at module insertion time (if a module).  There can only
277  * be one per module.
278  */
279 #define module_init(x)  __initcall(x);

So you can see that module_init defined as __initcall that defined as device_initcall that defined as __define_initcall("6",fn,6). Six here means initcall level. See below...

init/main.c contains the following:

711 extern initcall_t __initcall_start[];
712 extern initcall_t __initcall0_start[];
713 extern initcall_t __initcall1_start[];
714 extern initcall_t __initcall2_start[];
715 extern initcall_t __initcall3_start[];
716 extern initcall_t __initcall4_start[];
717 extern initcall_t __initcall5_start[];
718 extern initcall_t __initcall6_start[];
719 extern initcall_t __initcall7_start[];
720 extern initcall_t __initcall_end[];
721
722 static initcall_t *initcall_levels[] __initdata = {
723         __initcall0_start,
724         __initcall1_start,
725         __initcall2_start,
726         __initcall3_start,
727         __initcall4_start,
728         __initcall5_start,
729         __initcall6_start,
730         __initcall7_start,
731         __initcall_end,
732 };
733 
734 /* Keep these in sync with initcalls in include/linux/init.h */
735 static char *initcall_level_names[] __initdata = {
736         "early",
737         "core",
738         "postcore",
739         "arch",
740         "subsys",
741         "fs",
742         "device",
743         "late",
744 };
745 
746 static void __init do_initcall_level(int level)
747 {
748         extern const struct kernel_param __start___param[], __stop___param[];
749         initcall_t *fn;
750 
751         strcpy(static_command_line, saved_command_line);
752         parse_args(initcall_level_names[level],
753                    static_command_line, __start___param,
754                    __stop___param - __start___param,
755                    level, level,
756                    &repair_env_string);
757 
758         for (fn = initcall_levels[level]; fn < initcall_levels[level+1]; fn++)
759                 do_one_initcall(*fn);
760 }
761 
762 static void __init do_initcalls(void)
763 {
764         int level;
765 
766         for (level = 0; level < ARRAY_SIZE(initcall_levels) - 1; level++)
767                 do_initcall_level(level);
768 }

As you can see do_initcall simply iterates over all the initcall levels and calls do_initcall_level for each one that calls do_one_initcall for each level's entry.

Let's note also that kernel discards all the __init functions after execution. So they don't take place in memory after the kernel loads.

That's all.