ARM10C 78주차 후기

일시 : 2014.11.15 (78주차)

모임명 : NAVER개발자커뮤니티지원_10차ARM-C

장소 : 토즈 타워점

장소지원 : NAVER 개발자 커뮤니티 지원 프로그램

참여인원 : 3명

============

진도

지난시간에 이어 init_IRQ()->...->gic_of_init()->gic_init_bases()을 계속 분석합니다.
init_IRQ()->...->gic_of_init()->gic_init_bases();

irq_base = irq_alloc_descs(irq_start, 16, gic_irqs, numa_node_id());

early_irq_init()

irq_insert_desc(i, desc);
IRQ 0~15까지 RADIX-TREE를 이용하여 할당함.

irq_alloc_descs()->alloc_descs();

IRQ 16~160까지 RADIX-TREE를 이용하여 할당함.
우리는 0~15까지 할당했고, 16번째를 한다음. 64번째 IRQ할당을 분석.

===============

main.c::start_kernel()

asmlinkage void __init start_kernel(void)
{

...

	boot_cpu_init();
	// 현재 cpu(core id)를 얻어서 cpu_XXX_bits[] 의 cpu를 셋한다.

...

	setup_arch(&command_line);

...

	mm_init();
	// buddy와 slab 을 활성화 하고 기존 할당 받은 bootmem 은 buddy,
	// pcpu 메모리, vmlist 는 slab으로 이관

...

	rcu_init();
	// rcu 자료구조 bh, sched, preempt 를 각각 초기화 수행함

...

	/* init some links before init_ISA_irqs() */
	early_irq_init();
	// irq_desc 0 ~ 15 까지의 object을 할당 받고 초기화를 수행
	// allocated_irqs에 bit를 1로 세팅하고 radix tree에 각 irq_desc를 노트로 추가

	init_IRQ();

call: start_kernel()->init_IRQ()

irq.c::init_IRQ()

called: start_kernel()->init_IRQ()

init_IRQ();

// ARM10C 20141004
void __init init_IRQ(void)
{
	// CONFIG_OF=y, machine_desc->init_irq: __mach_desc_EXYNOS5_DT.init_irq: 0
	if (IS_ENABLED(CONFIG_OF) && !machine_desc->init_irq)
		irqchip_init();
	else
		machine_desc->init_irq();
}

call: start_kernel()->init_IRQ()->irqchip_init()

irqchip_init();

irqchip.h::irqchip_init()

called: start_kernel()->init_IRQ()->irqchip_init()

irqchip_init();

// ARM10C 20141004
extern struct of_device_id __irqchip_begin[];

// ARM10C 20141004
void __init irqchip_init(void)
{
	// exynos-combiner.c 에 정의된 함수를 사용하여 초기화 수행
	// __irqchip_begin: irqchip_of_match_exynos4210_combiner
	of_irq_init(__irqchip_begin);
}

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()

of_irq_init(__irqchip_begin);
//__irqchip_begin: irqchip_of_match_exynos4210_combiner

irqchip.h::irqchip_init()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()

of_irq_init(__irqchip_begin);
// __irqchip_begin: irqchip_of_match_exynos4210_combiner

void __init of_irq_init(const struct of_device_id *matches)
{
	struct device_node *np, *parent = NULL;
	// parent: NULL
	struct intc_desc *desc, *temp_desc;
	struct list_head intc_desc_list, intc_parent_list;

	INIT_LIST_HEAD(&intc_desc_list);
	// intc_desc_list 리스트 초기화 수행

	INIT_LIST_HEAD(&intc_parent_list);
	// intc_parent_list 리스트 초기화 수행

	// matches: irqchip_of_match_exynos4210_combiner
	for_each_matching_node(np, matches) {
	// for (np = of_find_matching_node(NULL, matches); np; np = of_find_matching_node(np, matches))

		// np: devtree에서 allnext로 순회 하면서 찾은 combiner node의 주소
		// of_find_property(devtree에서 allnext로 순회 하면서 찾은 combiner node의 주소, "interrupt-controller", NULL):
		// combiner node의 "interrupt-controller" property의 주소
		// np: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
		// of_find_property(devtree에서 allnext로 순회 하면서 찾은 gic node의 주소, "interrupt-controller", NULL):
		// gic node의 "interrupt-controller" property의 주소
		if (!of_find_property(np, "interrupt-controller", NULL))
			continue;
		/*
		 * Here, we allocate and populate an intc_desc with the node
		 * pointer, interrupt-parent device_node etc.
		 */
		// sizeof(struct intc_desc): 16 bytes, GFP_KERNEL: 0xD0
		// kzalloc(16, GFP_KERNEL: 0xD0): kmem_cache#30-o10
		// sizeof(struct intc_desc): 16 bytes, GFP_KERNEL: 0xD0
		// kzalloc(16, GFP_KERNEL: 0xD0): kmem_cache#30-o11
		desc = kzalloc(sizeof(*desc), GFP_KERNEL);
		// desc: kmem_cache#30-o10
		// desc: kmem_cache#30-o11

		// desc: kmem_cache#30-o10
		// desc: kmem_cache#30-o11
		if (WARN_ON(!desc))
			goto err;

		// desc->dev: (kmem_cache#30-o10)->dev, np: devtree에서 allnext로 순회 하면서 찾은 combiner node의 주소
		// desc->dev: (kmem_cache#30-o11)->dev, np: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
		desc->dev = np;
		// desc->dev: (kmem_cache#30-o10)->dev: devtree에서 allnext로 순회 하면서 찾은 combiner node의 주소
		// desc->dev: (kmem_cache#30-o11)->dev: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소

		// desc->interrupt_parent: (kmem_cache#30-o10)->interrupt_parent, np: devtree에서 allnext로 순회 하면서 찾은 combiner node의 주소
		// of_irq_find_parent(devtree에서 allnext로 순회 하면서 찾은 combiner node의 주소): gic node 주소
		// desc->interrupt_parent: (kmem_cache#30-o11)->interrupt_parent, np: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
		// of_irq_find_parent(devtree에서 allnext로 순회 하면서 찾은 gic node의 주소): gic node 주소
		desc->interrupt_parent = of_irq_find_parent(np);
		// desc->interrupt_parent: (kmem_cache#30-o10)->interrupt_parent: gic node 주소
		// desc->interrupt_parent: (kmem_cache#30-o11)->interrupt_parent: gic node 주소

		// desc->interrupt_parent: (kmem_cache#30-o10)->interrupt_parent: gic node 주소
		// np: devtree에서 allnext로 순회 하면서 찾은 combiner node의 주소
		// desc->interrupt_parent: (kmem_cache#30-o11)->interrupt_parent: gic node 주소
		// np: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
		if (desc->interrupt_parent == np)
			// desc->interrupt_parent: (kmem_cache#30-o11)->interrupt_parent: gic node 주소
			desc->interrupt_parent = NULL;
			// desc->interrupt_parent: (kmem_cache#30-o11)->interrupt_parent: NULL

		// &desc->list: &(kmem_cache#30-o10)->list
		// &desc->list: &(kmem_cache#30-o11)->list
		list_add_tail(&desc->list, &intc_desc_list);
		// intc_desc_list에 (kmem_cache#30-o10)->list를 tail에 추가
		// intc_desc_list에 (kmem_cache#30-o11)->list를 tail에 추가
	}

	// irqchip_of_match_exynos4210_combiner, irqchip_of_match_cortex_a15_gic 의
	// struct intc_desc 메모리 할당, intc_desc 맴버가 초기화 된 값이 intc_desc_list list의 tail로 추가됨

	// list_empty(&intc_desc_list): 0
	while (!list_empty(&intc_desc_list)) {
		list_for_each_entry_safe(desc, temp_desc, &intc_desc_list, list) {
		// for (desc = list_first_entry(&intc_desc_list, typeof(*desc), list),
		// 	temp_desc = list_next_entry(desc, list);
		//      &desc->list != (&intc_desc_list);
		//      desc = temp_desc, temp_desc = list_next_entry(temp_desc, list))

			// desc: kmem_cache#30-o10 (exynos4210_combiner), temp_desc: kmem_cache#30-o11 (cortex_a15_gic)
			// desc: kmem_cache#30-o11 (cortex_a15_gic), temp_desc: NULL

			const struct of_device_id *match;
			int ret;
			of_irq_init_cb_t irq_init_cb;

			// desc->interrupt_parent: (kmem_cache#30-o10)->interrupt_parent: gic node 주소, parent: NULL
			// desc->interrupt_parent: (kmem_cache#30-o11)->interrupt_parent: NULL, parent: NULL
			if (desc->interrupt_parent != parent)
				continue;
				// continue 수행 (exynos4210_combiner)

			// &desc->list: (kmem_cache#30-o11)->list
			list_del(&desc->list);
			// intc_desc_list에서 (kmem_cache#30-o11)->list를 삭제

			// matches: irqchip_of_match_cortex_a15_gic,
			// desc->dev: (kmem_cache#30-o11)->dev: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
			// of_match_node(cortex_a15_gic, devtree에서 allnext로 순회 하면서 찾은 gic node의 주소):
			// irqchip_of_match_cortex_a15_gic
			match = of_match_node(matches, desc->dev);
			// match: irqchip_of_match_cortex_a15_gic

			// match->data; irqchip_of_match_cortex_a15_gic.data: gic_of_init
			if (WARN(!match->data,
			    "of_irq_init: no init function for %s\n",
			    match->compatible)) {
				kfree(desc);
				continue;
			}

			// match->compatible: irqchip_of_match_cortex_a15_gic.compatible: "arm,cortex-a15-gic",
			// desc->dev: (kmem_cache#30-o11)->dev: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
			// desc->interrupt_parent: (kmem_cache#30-o11)->interrupt_parent: NULL
			pr_debug("of_irq_init: init %s @ %p, parent %p\n",
				 match->compatible,
				 desc->dev, desc->interrupt_parent);
			// "of_irq_init: init arm,cortex-a15-gic @ 0x(gic node의 주소), parent 0\n"

			// match->data; irqchip_of_match_cortex_a15_gic.data: gic_of_init
			irq_init_cb = (of_irq_init_cb_t)match->data;
			// irq_init_cb: gic_of_init

			// desc->dev: (kmem_cache#30-o11)->dev: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소,
			// desc->interrupt_parent: (kmem_cache#30-o11)->interrupt_parent: NULL
			// gic_of_init(devtree에서 allnext로 순회 하면서 찾은 gic node의 주소, NULL):
			ret = irq_init_cb(desc->dev, desc->interrupt_parent);

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()

ret = irq_init_cb(desc->dev, desc->interrupt_parent);
// __irqchip_begin: irqchip_of_match_exynos4210_combiner
// irq_init_cb = (of_irq_init_cb_t)match->data;
여기서 irq_init_cb: gic_of_init 로 되어 gic_of_init()를 실행한다.

irq_gic.c::gic_of_init()

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()

ret = irq_init_cb(desc->dev, desc->interrupt_parent);
// __irqchip_begin: irqchip_of_match_exynos4210_combiner
// irq_init_cb = (of_irq_init_cb_t)match->data;
여기서 irq_init_cb: gic_of_init 로 되어 gic_of_init()를 실행한다.

// ARM10C 20141018
// desc->dev: (kmem_cache#30-o11)->dev: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소,
// desc->interrupt_parent: (kmem_cache#30-o11)->interrupt_parent: NULL
int __init gic_of_init(struct device_node *node, struct device_node *parent)
{
	void __iomem *cpu_base;
	void __iomem *dist_base;
	u32 percpu_offset;
	int irq;

	// node: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
	if (WARN_ON(!node))
		return -ENODEV;

	// node: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
	// of_iomap(devtree에서 allnext로 순회 하면서 찾은 gic node의 주소, 0): 0xf0000000
	dist_base = of_iomap(node, 0);
	// dist_base: 0xf0000000


	// dist_base: 0xf000000
	WARN(!dist_base, "unable to map gic dist registers\n");

	// node: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
	// of_iomap(devtree에서 allnext로 순회 하면서 찾은 gic node의 주소, 1): 0xf002000
	cpu_base = of_iomap(node, 1);
	// cpu_base: 0xf0002000

	// cpu_base: 0xf0002000
	WARN(!cpu_base, "unable to map gic cpu registers\n");

	// node: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
	// of_property_read_u32(devtree에서 allnext로 순회 하면서 찾은 gic node의 주소, "cpu-offset", &percpu_offset):
	// 0이 아닌 err 값
	if (of_property_read_u32(node, "cpu-offset", &percpu_offset))
		percpu_offset = 0;
		// percpu_offset: 0

	// gic_cnt: 0, dist_base: 0xf0000000, cpu_base: 0xf0002000, percpu_offset: 0,
	// node: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
	gic_init_bases(gic_cnt, -1, dist_base, cpu_base, percpu_offset, node);

call: * call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()

gic_init_bases(gic_cnt, -1, dist_base, cpu_base, percpu_offset, node);

irq-gic.c::gic_init_bases()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()

gic_init_bases(gic_cnt, -1, dist_base, cpu_base, percpu_offset, node);
gic_cnt: 0, -1, dist_base: 0xf0000000, cpu_base: 0xf0002000, percpu_offset:0,
node:

// ARM10C 20141108
// gic_cnt: 0, -1, dist_base: 0xf0000000, cpu_base: 0xf0002000, percpu_offset: 0,
// node: devtree에서 allnext로 순회 하면서 찾은 gic node의 주소
void __init gic_init_bases(unsigned int gic_nr, int irq_start,
			   void __iomem *dist_base, void __iomem *cpu_base,
			   u32 percpu_offset, struct device_node *node)
{
	irq_hw_number_t hwirq_base;
	struct gic_chip_data *gic;
	int gic_irqs, irq_base, i;

	// gic_nr: 0, MAX_GIC_NR: 1
	BUG_ON(gic_nr >= MAX_GIC_NR);

	// gic_nr: 0
	gic = &gic_data[gic_nr];
	// gic: &gic_data[0]

#ifdef CONFIG_GIC_NON_BANKED // CONFIG_GIC_NON_BANKED=n
	if (percpu_offset) { /* Frankein-GIC without banked registers... */
		unsigned int cpu;

		gic->dist_base.percpu_base = alloc_percpu(void __iomem *);
		gic->cpu_base.percpu_base = alloc_percpu(void __iomem *);
		if (WARN_ON(!gic->dist_base.percpu_base ||
			    !gic->cpu_base.percpu_base)) {
			free_percpu(gic->dist_base.percpu_base);
			free_percpu(gic->cpu_base.percpu_base);
			return;
		}

		for_each_possible_cpu(cpu) {
			unsigned long offset = percpu_offset * cpu_logical_map(cpu);
			*per_cpu_ptr(gic->dist_base.percpu_base, cpu) = dist_base + offset;
			*per_cpu_ptr(gic->cpu_base.percpu_base, cpu) = cpu_base + offset;
		}

		gic_set_base_accessor(gic, gic_get_percpu_base);
	} else
#endif
	{			/* Normal, sane GIC... */
		// percpu_offset: 0
		WARN(percpu_offset,
		     "GIC_NON_BANKED not enabled, ignoring %08x offset!",
		     percpu_offset);
		// gic->dist_base.common_base: (&gic_data[0])->dist_base.common_base, dist_base: 0xf0000000
		gic->dist_base.common_base = dist_base;
		// gic->dist_base.common_base: (&gic_data[0])->dist_base.common_base: 0xf0000000

		// gic->cpu_base.common_base: (&gic_data[0])->cpu_base.common_base, cpu_base: 0xf0002000
		gic->cpu_base.common_base = cpu_base;
		// gic->cpu_base.common_base: (&gic_data[0])->cpu_base.common_base: 0xf0002000

		// gic: &gic_data[0]
		gic_set_base_accessor(gic, gic_get_common_base); // null function
	}

	/*
	 * Initialize the CPU interface map to all CPUs.
	 * It will be refined as each CPU probes its ID.
	 */
	// NR_GIC_CPU_IF: 8
	for (i = 0; i < NR_GIC_CPU_IF; i++)
		// i: 0
		gic_cpu_map[i] = 0xff;
		// gic_cpu_map[0]: 0xff
		// i: 1...7 까지 수행

	// gic_cpu_map[0...7]: 0xff

	/*
	 * For primary GICs, skip over SGIs.
	 * For secondary GICs, skip over PPIs, too.
	 */
	// gic_nr: 0, irq_start: -1
	if (gic_nr == 0 && (irq_start & 31) > 0) {
		hwirq_base = 16;
		// hwirq_base: 16

		// irq_start: -1
		if (irq_start != -1)
			irq_start = (irq_start & ~31) + 16;
	} else {
		hwirq_base = 32;
	}

	/*
	 * Find out how many interrupts are supported.
	 * The GIC only supports up to 1020 interrupt sources.
	 */
	// T.R.M: 8.3.2 Distributor register descriptions
	// Interrupt Controller Type Register:
	// b00100 Up to 160 interrupts, 128 external interrupt lines.
	//
	// gic: &gic_data[0], gic_data_dist_base(&gic_data[0]): 0xf0000000, GIC_DIST_CTR: 0x004
	// readl_relaxed(0xf0000000 + 0x004): 0x0000FC24
	gic_irqs = readl_relaxed(gic_data_dist_base(gic) + GIC_DIST_CTR) & 0x1f;
	// gic_irqs: 0x4

// 2014/11/08 종료

	gic_irqs = (gic_irqs + 1) * 32;
	if (gic_irqs > 1020)
		gic_irqs = 1020;
	gic->gic_irqs = gic_irqs;

	gic_irqs -= hwirq_base; /* calculate # of irqs to allocate */
	irq_base = irq_alloc_descs(irq_start, 16, gic_irqs, numa_node_id());

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()

irq_base = irq_alloc_descs(irq_start, 16, gic_irqs, numa_node_id());

irq.h::irq_alloc_descs()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()

irq_base = irq_alloc_descs(irq_start, 16, gic_irqs, numa_node_id());

#define irq_alloc_descs(irq, from, cnt, node)	\
	__irq_alloc_descs(irq, from, cnt, node, THIS_MODULE)

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()

irqdesc.c::__irq_alloc_descs()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()

int __ref
__irq_alloc_descs(int irq, unsigned int from, unsigned int cnt, int node,
		  struct module *owner)
{
	int start, ret;

	if (!cnt)
		return -EINVAL;

	if (irq >= 0) {
		if (from > irq)
			return -EINVAL;
		from = irq;
	}

	mutex_lock(&sparse_irq_lock);

	start = bitmap_find_next_zero_area(allocated_irqs, IRQ_BITMAP_BITS,
					   from, cnt, 0);

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()

bitmap.c::bitmap_find_next_zero_area()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()

unsigned long bitmap_find_next_zero_area(unsigned long *map,
					 unsigned long size,
					 unsigned long start,
					 unsigned int nr,
					 unsigned long align_mask)
{
	unsigned long index, end, i;
again:
	index = find_next_zero_bit(map, size, start);

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_zero_bit()

bitops.h::find_next_zero_bit()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_zero_bit()

index = find_next_zero_bit(map, size, start);

#define find_next_zero_bit(p,sz,off)	_find_next_zero_bit_le(p,sz,off)

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_zero_bit()->_find_next_zero_bit_le()

findbit.S::_find_next_zero_bit_le()

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_zero_bit()->_find_next_zero_bit_le()

ENTRY(_find_next_zero_bit_le)
		teq	r1, #0
		beq	3b
		ands	ip, r2, #7
		beq	1b			@ If new byte, goto old routine
 ARM(		ldrb	r3, [r0, r2, lsr #3]	)
 THUMB(		lsr	r3, r2, #3		)
 THUMB(		ldrb	r3, [r0, r3]		)
		eor	r3, r3, #0xff		@ now looking for a 1 bit
		movs	r3, r3, lsr ip		@ shift off unused bits
		bne	.L_found
		orr	r2, r2, #7		@ if zero, then no bits here
		add	r2, r2, #1		@ align bit pointer
		b	2b			@ loop for next bit
ENDPROC(_find_next_zero_bit_le)

return start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_zero_bit()

bitmap.c::bitmap_find_next_zero_area()

return: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_zero_bit()

unsigned long bitmap_find_next_zero_area(unsigned long *map,
					 unsigned long size,
					 unsigned long start,
					 unsigned int nr,
					 unsigned long align_mask)
{
	unsigned long index, end, i;
again:
	index = find_next_zero_bit(map, size, start);

	index = __ALIGN_MASK(index, align_mask);

	end = index + nr;
	if (end > size)
		return end;
	// map: allocated_irqs, end: 160, index: 16
	i = find_next_bit(map, end, index);
	// find_next_bit: 160

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_bit()

bitops.h::find_next_bit()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_bit()

#define find_next_bit(p,sz,off)		_find_next_bit_le(p,sz,off)

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_bit()->_find_next_bit_le()

findbit.S::_find_next_bit_le()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_bit()->_find_next_bit_le()

ENTRY(_find_next_bit_le)
		teq	r1, #0
		beq	3b
		ands	ip, r2, #7
		beq	1b			@ If new byte, goto old routine
 ARM(		ldrb	r3, [r0, r2, lsr #3]	)
 THUMB(		lsr	r3, r2, #3		)
 THUMB(		ldrb	r3, [r0, r3]		)
		movs	r3, r3, lsr ip		@ shift off unused bits
		bne	.L_found
		orr	r2, r2, #7		@ if zero, then no bits here
		add	r2, r2, #1		@ align bit pointer
		b	2b			@ loop for next bit
ENDPROC(_find_next_bit_le)

return start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_bit()->_find_next_bit_le()
return start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_bit()

bitmap.c::bitmap_find_next_zero_area()

return start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->bitmap_find_next_zero_area()->find_next_bit()

unsigned long bitmap_find_next_zero_area(unsigned long *map,
					 unsigned long size,
					 unsigned long start,
					 unsigned int nr,
					 unsigned long align_mask)
{
	unsigned long index, end, i;
again:
	index = find_next_zero_bit(map, size, start);

	index = __ALIGN_MASK(index, align_mask);

	end = index + nr;
	if (end > size)
		return end;
	// map: allocated_irqs, end: 160, index: 16
	i = find_next_bit(map, end, index);
	// find_next_bit: 160

    // 
	if (i < end) {
		start = i + 1;
		goto again;
	}
	// index: 16
	return index;
}
EXPORT_SYMBOL(bitmap_find_next_zero_area);

return start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs(): 16

irqdesc.c::__irq_alloc_descs()

return: 16: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()

start: 16

int __ref
__irq_alloc_descs(int irq, unsigned int from, unsigned int cnt, int node,
		  struct module *owner)
{
...
	start = bitmap_find_next_zero_area(allocated_irqs, IRQ_BITMAP_BITS,
					   from, cnt, 0);
    // start: 16

    // EEIST: 17
	ret = -EEXIST;
	// ret: 17

    // irq: -1, start: 16
	if (irq >=0 && start != irq)
		goto err;

    // start: 16, cnt: 144 > nr_irqs: 16
	if (start + cnt > nr_irqs) {
	    // 
		ret = irq_expand_nr_irqs(start + cnt);
		if (ret)
			goto err;
	}

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()

ret = irq_expand_nr_irqs(start + cnt);

irqdesc.c::irq_expand_nr_irqs()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()

ret = irq_expand_nr_irqs(start + cnt);
start: 16, cnt: 144

static int irq_expand_nr_irqs(unsigned int nr)
{
    // nr: 160, IRQ_BITMAP_BITS: 8212
	if (nr > IRQ_BITMAP_BITS)
		return -ENOMEM;
		
	// nr_irqs:
	nr_irqs = nr;
	// nr_irqs: 160
	return 0;
}

return: 160: * called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()

nr_irqs: 160으로 바꿈.

irqdesc.c::__irq_alloc_descs()

return: 160: * called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()

int __ref
__irq_alloc_descs(int irq, unsigned int from, unsigned int cnt, int node,
		  struct module *owner)
{
...

    // start: 16, cnt: 144 > nr_irqs: 16
	if (start + cnt > nr_irqs) {
	    // 
		ret = irq_expand_nr_irqs(start + cnt);
		// nr_irqs: 160으로 바뀜.

        // ret: 0
		if (ret)
			goto err;
	}
	bitmap_set(allocated_irqs, start, cnt);

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt);

bitmap.c::bitmap_set()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt);

void bitmap_set(unsigned long *map, int start, int nr)
{
    // map: allocated_irqs, start: 16, nr: 144
	unsigned long *p = map + BIT_WORD(start);

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)->BIT_WORD();

bitops.h::BIT_WORD()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)->BIT_WORD();

#define BIT_WORD(nr)		((nr) / BITS_PER_LONG)

return (16/32): 0: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)->BIT_WORD();

bitmap.c::bitmap_set()

return (16/32): 0: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)->BIT_WORD();

void bitmap_set(unsigned long *map, int start, int nr)
{
    // map: allocated_irqs, start: 16, nr: 144
	unsigned long *p = map + BIT_WORD(start);
	// p: allocated_irqs[0]

    // start: 16, nr: 144
    const int size = start + nr;
	// size: 160

    // BITS_PER_LONG: 32, (start: 16 % BITS_PER_LONG: 32)
	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
	// bits_to_set: (32 - 16): 16

    // start: 16, BITMAP_FIRST_WORD_MASK
	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)->BITMAP_FIRST_WORD_MASK(start:16)

bitmap.h::BITMAP_FIRST_WORD_MASK()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)->BITMAP_FIRST_WORD_MASK(start:16)

#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))

return: 0xffff0000: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)->BITMAP_FIRST_WORD_MASK(start:16)

bitmap.c::bitmap_set()

return: 0xffff0000: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)->BITMAP_FIRST_WORD_MASK(start:16)

void bitmap_set(unsigned long *map, int start, int nr)
{
    // map: allocated_irqs, start: 16, nr: 144
	unsigned long *p = map + BIT_WORD(start);
	// p: allocated_irqs[0]

    // start: 16, nr: 144
    const int size = start + nr;
	// size: 160

    // BITS_PER_LONG: 32, (start: 16 % BITS_PER_LONG: 32)
	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
	// bits_to_set: (32 - 16): 16

    // start: 16, BITMAP_FIRST_WORD_MASK
	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);

bitmap.c::bitmap_set()

return 0xffff0000: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)->BITMAP_FIRST_WORD_MASK(start:16)

void bitmap_set(unsigned long *map, int start, int nr)
{
    // map: allocated_irqs, start: 16, nr: 144
	unsigned long *p = map + BIT_WORD(start);
	// p: allocated_irqs[0]

    // start: 16, nr: 144
    const int size = start + nr;
	// size: 160

    // BITS_PER_LONG: 32, (start: 16 % BITS_PER_LONG: 32)
	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
	// bits_to_set: (32 - 16): 16

    // start: 16, BITMAP_FIRST_WORD_MASK
	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
	// mask_to_set: BITMAP_FIRST_WORD_MASK: 0xffff0000

    // nr: 144 bits_to_set: 16
	while (nr - bits_to_set >= 0) {
	    // *p: allocated_irqs[0]: 0x0000ffff, mask_to_set: 0xffff0000
		*p |= mask_to_set;
		// *P: 0xffffffff
		
		// nr: 144, bits_to_set: 16
		nr -= bits_to_set;
		// nr: 128

        // bits_to_set: 16
		bits_to_set = BITS_PER_LONG;
		// bits_to_set: BITS_PER_LONG: 32

        // mask_to_set: 0xffff0000, ~0UL: 0xffffffff
		mask_to_set = ~0UL;
		// mask_to_set: 0xffffffff

        // p: &allocated_irqs[0]
		p++;
		// p: &allocated_irqs[1]
	}
	// 144, 128, 96, 64, 32, 0: 160개를 32word단위로 할당하므로 5번 반복
	// allocated_irqs[0,1,2,3,4,5]
	
	if (nr) {
		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
		*p |= mask_to_set;
	}
}
EXPORT_SYMBOL(bitmap_set);

allocated_irqs: 16~ 144개 bit을 1로 설정.
retuen: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)

irqdesc.c::__irq_alloc_descs()

retuen: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_expand_nr_irqs()->bitmap_set(allocated_irqs, start, cnt)

int __ref
__irq_alloc_descs(int irq, unsigned int from, unsigned int cnt, int node,
		  struct module *owner)
{
...

	// start: 16, cnt: 144
	bitmap_set(allocated_irqs, start, cnt);
	// bitmap_set에서 한일:
	// allocated_irqs 의 16 bit 부터 144 bit를 1로 set

	mutex_unlock(&sparse_irq_lock);
	// sparse_irq_lock을 이용한 mutex unlock 수행

	// start: 16, cnt: 144, node: 0, owner: NULL
	return alloc_descs(start, cnt, node, owner);

err:
	mutex_unlock(&sparse_irq_lock);
	return ret;
}
EXPORT_SYMBOL_GPL(__irq_alloc_descs);

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->alloc_descs()

irqdesc.c::alloc_descs()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->alloc_descs()
struct irq_desc

struct irq_desc {
	struct irq_data		irq_data;
	unsigned int __percpu	*kstat_irqs;
	irq_flow_handler_t	handle_irq;

	struct irqaction	*action;	/* IRQ action list */
	unsigned int		status_use_accessors;
	unsigned int		core_internal_state__do_not_mess_with_it;
	unsigned int		depth;		/* nested irq disables */
	unsigned int		wake_depth;	/* nested wake enables */
	unsigned int		irq_count;	/* For detecting broken IRQs */
	unsigned long		last_unhandled;	/* Aging timer for unhandled count */
	unsigned int		irqs_unhandled;
	raw_spinlock_t		lock;
	struct cpumask		*percpu_enabled;

	const struct cpumask	*affinity_hint;
	struct irq_affinity_notify *affinity_notify;

	cpumask_var_t		pending_mask;

	unsigned long		threads_oneshot;
	atomic_t		threads_active;
	wait_queue_head_t       wait_for_threads;

	struct proc_dir_entry	*dir;

	int			parent_irq;
	struct module		*owner;
	const char		*name;
} ____cacheline_internodealigned_in_smp;

// ARM10C 20141115
// start: 16, cnt: 144, node: 0, owner: NULL
static int alloc_descs(unsigned int start, unsigned int cnt, int node,
		       struct module *owner)
{
	struct irq_desc *desc;
	int i;

	// cnt: 144
	for (i = 0; i < cnt; i++) {
		// i: 0, start: 16, node: 0, owner: NULL
		// alloc_desc(16, 0, NULL): kmem_cache#28-oX
		// i: 48, start: 16, node: 0, owner: NULL
		// alloc_desc(64, 0, NULL): kmem_cache#28-oX (irq 64)
		desc = alloc_desc(start + i, node, owner);
		// desc: kmem_cache#28-oX
		// desc: kmem_cache#28-oX (irq 64)

alloc_desc(16)가 한일

irq_data.irq: 16으로 할당.
alloc_desc(16)에서 한일:
(kmem_cache#28-oX)->kstat_irqs: pcp 4 byte 공간
(kmem_cache#28-oX)->lock 을 이용한 spinlock 초기화 수행
(kmem_cache#28-oX)->irq_data.irq: 16
(kmem_cache#28-oX)->irq_data.chip: &no_irq_chip
(kmem_cache#28-oX)->irq_data.chip_data: NULL
(kmem_cache#28-oX)->irq_data.handler_data: NULL
(kmem_cache#28-oX)->irq_data.msi_desc: NULL
(kmem_cache#28-oX)->status_use_accessors: 0xc00
(&(kmem_cache#28-oX)->irq_data)->state_use_accessors: 0x10000
(kmem_cache#28-oX)->handle_irq: handle_bad_irq
(kmem_cache#28-oX)->depth: 1
(kmem_cache#28-oX)->irq_count: 0
(kmem_cache#28-oX)->irqs_unhandled: 0
(kmem_cache#28-oX)->name: NULL
(kmem_cache#28-oX)->owner: null
[pcp0...3] (kmem_cache#28-oX)->kstat_irqs: 0
(kmem_cache#28-oX)->irq_data.node: 0
(kmem_cache#28-oX)->irq_data.affinity.bits[0]: 0xF

alloc_desc(64)에서 한일:

(kmem_cache#28-oX)->kstat_irqs: pcp 4 byte 공간
(kmem_cache#28-oX)->lock 을 이용한 spinlock 초기화 수행
(kmem_cache#28-oX)->irq_data.irq: 64
(kmem_cache#28-oX)->irq_data.chip: &no_irq_chip
(kmem_cache#28-oX)->irq_data.chip_data: NULL
(kmem_cache#28-oX)->irq_data.handler_data: NULL
(kmem_cache#28-oX)->irq_data.msi_desc: NULL
(kmem_cache#28-oX)->status_use_accessors: 0xc00
(&(kmem_cache#28-oX)->irq_data)->state_use_accessors: 0x10000
(kmem_cache#28-oX)->handle_irq: handle_bad_irq
(kmem_cache#28-oX)->depth: 1
(kmem_cache#28-oX)->irq_count: 0
(kmem_cache#28-oX)->irqs_unhandled: 0
(kmem_cache#28-oX)->name: NULL
(kmem_cache#28-oX)->owner: null
[pcp0...3] (kmem_cache#28-oX)->kstat_irqs: 0
(kmem_cache#28-oX)->irq_data.node: 0
(kmem_cache#28-oX)->irq_data.affinity.bits[0]: 0xF

// ARM10C 20141115
// start: 16, cnt: 144, node: 0, owner: NULL
static int alloc_descs(unsigned int start, unsigned int cnt, int node,
		       struct module *owner)
{
	struct irq_desc *desc;
	int i;

	// cnt: 144
	for (i = 0; i < cnt; i++) {
		// i: 0, start: 16, node: 0, owner: NULL
		// alloc_desc(16, 0, NULL): kmem_cache#28-oX
		// i: 48, start: 16, node: 0, owner: NULL
		// alloc_desc(64, 0, NULL): kmem_cache#28-oX (irq 64)
		desc = alloc_desc(start + i, node, owner);
		// desc: kmem_cache#28-oX
		// desc: kmem_cache#28-oX (irq 64)

		// desc: kmem_cache#28-oX
		// desc: kmem_cache#28-oX (irq 64)
		if (!desc)
			goto err;

		mutex_lock(&sparse_irq_lock);
		// sparse_irq_lock을 이용한 mutex lock 수행
		// sparse_irq_lock을 이용한 mutex lock 수행

		// i: 0, start: 16, desc: kmem_cache#28-oX, irq_insert_desc(16, kmem_cache#28-oX): 0
		// i: 48, start: 16, desc: kmem_cache#28-oX (irq 64), irq_insert_desc(48, kmem_cache#28-oX (irq 64)): 0
		irq_insert_desc(start + i, desc);

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_insert_desc()

irq_insert_desc(start + i, desc);

irqdesc.c::irq_insert_desc()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_insert_desc()

irq_insert_desc(start + i, desc);

static void irq_insert_desc(unsigned int irq, struct irq_desc *desc)
{
	// irq: 0, desc: kmem_cache#28-o0
	radix_tree_insert(&irq_desc_tree, irq, desc);
	// radix tree에 kmem_cache#28-o0를 노드로 추가
}

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_insert_desc()->radix_tree_insert()

radix_tree_insert(&irq_desc_tree, irq, desc);

radix-tree.c::radix_tree_insert()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_insert_desc()->radix_tree_insert()

// ARM10C 20141004
// sizeof(struct radix_tree_node): 296 bytes
struct radix_tree_node {
	unsigned int	height;		/* Height from the bottom */
	unsigned int	count;
	union {
		struct radix_tree_node *parent;	/* Used when ascending tree */
		struct rcu_head	rcu_head;	/* Used when freeing node */
	};
	// RADIX_TREE_MAP_SIZE: 64
	void __rcu	*slots[RADIX_TREE_MAP_SIZE];
	// RADIX_TREE_MAX_TAGS: 3, RADIX_TREE_TAG_LONGS: 2
	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

// &irq_desc_tree, irq: 0, desc: kmem_cache#28-o0
int radix_tree_insert(struct radix_tree_root *root,
			unsigned long index, void *item)
{
	struct radix_tree_node *node = NULL, *slot;
	unsigned int height, shift;
	int offset;
	int error;

    // item: kmem_cache#28-o0, 
	BUG_ON(radix_tree_is_indirect_ptr(item));

call: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_insert_desc()->radix_tree_insert()->radix_tree_is_indirect_ptr()

radix-tree.h::radix_tree_is_indirect_ptr()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_insert_desc()->radix_tree_insert()->radix_tree_is_indirect_ptr()

static inline int radix_tree_is_indirect_ptr(void *ptr)
{
    // ptr: kmem_cache#28-o0, RADIX_TREE_INDIRECT_PTR: 1
	return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
}

return : 홀수 주소가 나오면 문제가 발생함(버그)

radix-tree.c::radix_tree_insert()

returned: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_insert_desc()->radix_tree_insert()->radix_tree_is_indirect_ptr()

// &irq_desc_tree, irq: 0, desc: kmem_cache#28-o0
int radix_tree_insert(struct radix_tree_root *root,
			unsigned long index, void *item)
{
	struct radix_tree_node *node = NULL, *slot;
	unsigned int height, shift;
	int offset;
	int error;

    // item: kmem_cache#28-o0, 
	BUG_ON(radix_tree_is_indirect_ptr(item));
    // item:이 홀수주소라면 버그로 체크함.

	/* Make sure the tree is high enough.  */
	// root->height: (&irq_desc_tree)->height: 0
	if (index > radix_tree_maxindex(root->height)) {
		error = radix_tree_extend(root, index);
		if (error)
			return error;
	}

return: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_insert_desc()->radix_tree_insert()->radix_tree_maxindex()

radix-tree.c::radix_tree_maxindex()

called: start_kernel()->init_IRQ()->irqchip_init()->of_irq_init()->irq_init_cb()->gic_of_init()->gic_init_bases()->irq_alloc_descs()->__irq_alloc_descs()->irq_insert_desc()->radix_tree_insert()->radix_tree_maxindex()

// &irq_desc_tree, irq: 0, desc: kmem_cache#28-o0
int radix_tree_insert(struct radix_tree_root *root,
			unsigned long index, void *item)
{
...

	/* Make sure the tree is high enough.  */
	// root->height: *&irq_desc_tree)->height: 0
	// radix_tree_maxindex(0)
	if (index > radix_tree_maxindex(root->height)) {
		error = radix_tree_extend(root, index);
		if (error)
			return error;
	}

    // root->rnode: 
	slot = indirect_to_ptr(root->rnode);

radix-tree.c::indirect_to_ptr()

static inline void *indirect_to_ptr(void *ptr)
{
    // ptr: NULL, RADIX_TREE_INDIRECT_PTR: 1
	return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
	// return NULL
}

radix-tree.c::radix_tree_insert()

// &irq_desc_tree, irq: 0, desc: kmem_cache#28-o0
int radix_tree_insert(struct radix_tree_root *root,
			unsigned long index, void *item)
{
...
    // root->rnode: NULL
	slot = indirect_to_ptr(root->rnode);
	// slot: NULL

    // height: root->height: 0
	height = root->height;
	// height: 0

    // height: 0, RADIX_TREE_MAP_SHIFT: 6
	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
	// shift: 0xfffffffa

	offset = 0;			/* uninitialised var warning */
	// offset: 0
	
	while (height > 0) {
		if (slot == NULL) {
			/* Have to add a child node.  */
			if (!(slot = radix_tree_node_alloc(root)))
				return -ENOMEM;
			slot->height = height;
			slot->parent = node;
			if (node) {
				rcu_assign_pointer(node->slots[offset], slot);
				node->count++;
			} else
				rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
		}

		/* Go a level down */
		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
		node = slot;
		slot = node->slots[offset];
		shift -= RADIX_TREE_MAP_SHIFT;
		height--;
	}

    // slot: NULL
	if (slot != NULL)
		return -EEXIST;

    // node: NULL
	if (node) {
		node->count++;
		rcu_assign_pointer(node->slots[offset], item);
		BUG_ON(tag_get(node, 0, offset));
		BUG_ON(tag_get(node, 1, offset));
	} else {
	    // root->rnode: (&irq_desc_tree)->rnode: NULL, item: &((GIC))->list
		rcu_assign_pointer(root->rnode, item);
		BUG_ON(root_tag_get(root, 0));
		BUG_ON(root_tag_get(root, 1));
	}

	return 0;
}
EXPORT_SYMBOL(radix_tree_insert);

call: rcu_assign_pointer(root->rnode, item);

rcupdate.h::rcu_assign_pointer()

#define rcu_assign_pointer(p, v)		\
	__rcu_assign_pointer((p), (v), __rcu)

p: root->rnode: (&irq_desc_tree)->rnode: NULL,
v: item: &((GIC))->list

// __rcu_assign_pointer((&irq_desc_tree)->rnode, &((GIC))->list, ""):
// do {
//	  smp_wmb(); // dmb();
//	  ((&irq_desc_tree)->rnode = (typeof(&((GIC))->list) __force *)(&((GIC))->list);
// } while (0)
//
// *nl: (&cpu_chain)->head: &page_alloc_cpu_notify_nb, n: &((GIC))->list
// #define rcu_assign_pointer((&cpu_chain)->head, &slab_notifier:
// do {
//	  smp_wmb(); // dmb();
//	  (&irq_desc_tree)->rnode = (typeof(&((GIC))->list) __force *)(&((GIC))->list);
// } while (0)

radix-tree.c::radix_tree_insert()

// &irq_desc_tree, irq: 0, desc: kmem_cache#28-o0
int radix_tree_insert(struct radix_tree_root *root,
			unsigned long index, void *item)
{
...

    // node: NULL
	if (node) {
		node->count++;
		rcu_assign_pointer(node->slots[offset], item);
		BUG_ON(tag_get(node, 0, offset));
		BUG_ON(tag_get(node, 1, offset));
	} else {
	    // root->rnode: (&irq_desc_tree)->rnode: NULL, item: &((GIC))->list
		rcu_assign_pointer(root->rnode, item);
		BUG_ON(root_tag_get(root, 0));
		BUG_ON(root_tag_get(root, 1));
	}

	return 0;
}
EXPORT_SYMBOL(radix_tree_insert);

radix-tree.c::root_tag_get()

static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
{
    // __GFP_BITS_SHIFT: 25
	return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
	// return 0
}

return 0

radix-tree.c::root_tag_get()

static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
{
    // __GFP_BITS_SHIFT: 25
	return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
	// return 0
}

return 0

radix-tree.c::radix_tree_insert()

// &irq_desc_tree, irq: 0, desc: kmem_cache#28-o0
int radix_tree_insert(struct radix_tree_root *root,
			unsigned long index, void *item)
{
...

    // node: NULL
	if (node) {
		node->count++;
		rcu_assign_pointer(node->slots[offset], item);
		BUG_ON(tag_get(node, 0, offset));
		BUG_ON(tag_get(node, 1, offset));
	} else {
	    // root->rnode: (&irq_desc_tree)->rnode: NULL, item: &((GIC))->list
		rcu_assign_pointer(root->rnode, item);
		// ... 수정...
		BUG_ON(root_tag_get(root, 0));
		// BUG_ON(return 0)
		BUG_ON(root_tag_get(root, 1));
		// BUG_ON(return 0)
	}

	return 0;
}
EXPORT_SYMBOL(radix_tree_insert);

return 0

radix-tree.c::radix_tree_insert()

// ARM10C 20141004
// &irq_desc_tree, irq: 0, desc: kmem_cache#28-o0
// &irq_desc_tree, irq: 1, desc: kmem_cache#28-o1
int radix_tree_insert(struct radix_tree_root *root,
			unsigned long index, void *item)
{
	struct radix_tree_node *node = NULL, *slot;
	unsigned int height, shift;
	int offset;
	int error;

	BUG_ON(radix_tree_is_indirect_ptr(item));

	/* Make sure the tree is high enough.  */
	if (index > radix_tree_maxindex(root->height)) {
	    // root: *irq_desc_tree, index: 1
		error = radix_tree_extend(root, index);
		if (error)
			return error;
	}

radix-tree.c::radix_tree_extend()

// root: *irq_desc_tree, index: 1
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
	struct radix_tree_node *node;
	struct radix_tree_node *slot;
	unsigned int height;
	int tag;

	/* Figure out what the height should be.  */
	// height: *irq_desc_tree->height + 1
	height = root->height + 1;
	
	while (index > radix_tree_maxindex(height))
		height++;

radix-tree.c::radix_tree_maxindex()

static inline unsigned long radix_tree_maxindex(unsigned int height)
{
	return height_to_maxindex[height];
	// return 63
}

radix-tree.c::radix_tree_extend()

// root: *irq_desc_tree, index: 1
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
	struct radix_tree_node *node;
	struct radix_tree_node *slot;
	unsigned int height;
	int tag;

	/* Figure out what the height should be.  */
	// height: *irq_desc_tree->height + 1
	height = root->height + 1;
	
	while (index > radix_tree_maxindex(height))
		height++;
		// height: 64

    // 
	if (root->rnode == NULL) {
		root->height = height;
		goto out;
	}

	do {
		unsigned int newheight;
		// root: *irq_desc_tree
		if (!(node = radix_tree_node_alloc(root)))
			return -ENOMEM;

radix-tree.c::radix_tree_node_alloc()

static struct radix_tree_node *
radix_tree_node_alloc(struct radix_tree_root *root)
{
	struct radix_tree_node *ret = NULL;
	gfp_t gfp_mask = root_gfp_mask(root);

radix-tree.c::root_gfp_mask()

static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
{
	return root->gfp_mask & __GFP_BITS_MASK;
	// return .. 수정..
}

radix-tree.c::radix_tree_node_alloc()

static struct radix_tree_node *
radix_tree_node_alloc(struct radix_tree_root *root)
{
	struct radix_tree_node *ret = NULL;
	gfp_t gfp_mask = root_gfp_mask(root);
	// 

	/*
	 * Preload code isn't irq safe and it doesn't make sence to use
	 * preloading in the interrupt anyway as all the allocations have to
	 * be atomic. So just do normal allocation when in interrupt.
	 */
	// gfp_mask: GFP_KERNEL: 0xD0, __GFP_WAIT_: 0x10u, in_interrupt(): 0
	if (!(gfp_mask & __GFP_WAIT) && !in_interrupt()) {
		struct radix_tree_preload *rtp;

		/*
		 * Provided the caller has preloaded here, we will always
		 * succeed in getting a node here (and never reach
		 * kmem_cache_alloc)
		 */
		rtp = &__get_cpu_var(radix_tree_preloads);
		if (rtp->nr) {
			ret = rtp->nodes[rtp->nr - 1];
			rtp->nodes[rtp->nr - 1] = NULL;
			rtp->nr--;
		}
	}
	// ret: NULL
	if (ret == NULL)
	    // radix_tree_node_cachep: kmem_cache#20-o0, gfp_mask: GFP_KERNEL: 0xD0
		ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
		// ret: radix_tree_node_cachep: kmem_cache#20-o0

    // ret: radix_tree_node_cachep: kmem_cache#20-o0
	// radix_tree_is_indirect_ptr(kmem_cache#20-o0): not 0
	BUG_ON(radix_tree_is_indirect_ptr(ret));

	return ret;
	// return ret: radix_tree_node_cachep: kmem_cache#20-o0
}

return ret: radix_tree_node_cachep: kmem_cache#20-o0

radix-tree.c::radix_tree_extend()

return ret: radix_tree_node_cachep: kmem_cache#20-o0

// root: *irq_desc_tree, index: 1
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
...
	do {
		unsigned int newheight;
		if (!(node = radix_tree_node_alloc(root)))
			return -ENOMEM;

		/* Propagate the aggregated tag info into the new root */
		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
		    // root: &irq_desc_tree, tag: 0
			// root_tag_get(root: &irq_desc_tree, tag: 0): 0
			// root_tag_get(root: &irq_desc_tree, tag: 1): 0
			// root_tag_get(root: &irq_desc_tree, tag: 2): 0
			if (root_tag_get(root, tag))
				tag_set(node, tag, 0);
		}
		/* Increase the height.  */
		// root->height: &irq_desc_tree->height, + 1
		newheight = root->height+1;
		// newheight: 1
		node->height = newheight;
		// node->height: kmem_cache#20-o0->height: newheight: 1
		node->count = 1;
		// node->count: kmem_cache#20-o0->count: 1
		node->parent = NULL;
		// node->parent: kmem_cache#20-o0->parent: NULL
		slot = root->rnode;
		// slot: (&irq_desc_tree)->rnode: 
		if (newheight > 1) {
			slot = indirect_to_ptr(slot);
			slot->parent = node;
		}
		
		node->slots[0] = slot;
		node = ptr_to_indirect(node);

radix-reee.c::ptr_to_indirect()

static inline void *ptr_to_indirect(void *ptr)
{
	return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
}

radix-tree.c::radix_tree_extend()

return ret: radix_tree_node_cachep: kmem_cache#20-o0

// root: *irq_desc_tree, index: 1
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
...
	do {
		unsigned int newheight;
		if (!(node = radix_tree_node_alloc(root)))
			return -ENOMEM;

...

		node->slots[0] = slot;
		node = ptr_to_indirect(node);
		// node: ptr_to_indirect()

        // root->rnode:
		// node: 
		rcu_assign_pointer(root->rnode, node);
		// rcu_assign_pointer()

        // root->height: 0 
		root->height = newheight;
		// root->height: 1
	// height: 1 , root->height: 1
	} while (height > root->height);
out:
	return 0;
}

return 0

radix-tree.c::radix_tree_insert()

return: radix_tree_extent()

radix_tree_node_cachep를 사용한 radix_tree_node용 메모리 할당: kmem_cache#20-o0

// ARM10C 20141004
// &irq_desc_tree, irq: 0, desc: kmem_cache#28-o0
// &irq_desc_tree, irq: 1, desc: kmem_cache#28-o1

int radix_tree_insert(struct radix_tree_root *root,
			unsigned long index, void *item)
{
	struct radix_tree_node *node = NULL, *slot;
	unsigned int height, shift;
	int offset;
	int error;

	BUG_ON(radix_tree_is_indirect_ptr(item));

	/* Make sure the tree is high enough.  */
	if (index > radix_tree_maxindex(root->height)) {
		error = radix_tree_extend(root, index);
		// 내용 추가
		if (error)
			return error;
	}

    // root->rnode: 
	slot = indirect_to_ptr(root->rnode);

	height = root->height;
	shift = (height-1) * RADIX_TREE_MAP_SHIFT;

	offset = 0;			/* uninitialised var warning */
	while (height > 0) {
		if (slot == NULL) {
			/* Have to add a child node.  */
			if (!(slot = radix_tree_node_alloc(root)))
				return -ENOMEM;
			slot->height = height;
			slot->parent = node;
			if (node) {
				rcu_assign_pointer(node->slots[offset], slot);
				node->count++;
			} else
				rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
		}

		/* Go a level down */
		// offset: 0, index: 1, shift: 0, 
		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
		// offset: (1 >> 0) & 0x3f : 1

        // slot: kmem_cache#20-o0(RADIX_LSB: 0)
		node = slot;
		// node: kmem_cache#20-o0

        // node->slot[offset]: (kmem_cache#20-o0(RADIX_LSB:0)->slot[1]
		slot = node->slots[offset];
		// slot: (kmem_cache#20-o0(RADIX_LSB:0))->slot[1]: NULL

        // RADIX_TREE_MAP_SHIFT: 6
		shift -= RADIX_TREE_MAP_SHIFT;
		// shift: 0xfffffffa

        // height: 1
		height--;
		// height: 0
	}
	
    // slot: (kmem_cache#20-o0(RADIX_LSB:0)->slot[1]: NULL
	if (slot != NULL)
		return -EEXIST;

    // node: kmem_cache#20-o0(RADIX_LSB:0)
	if (node) {
	    // node->count: kmem_cache#20-o0(RADIX_LSB:0)->count: 1
		node->count++;
	    // node->count: kmem_cache#20-o0(RADIX_LSB:0)->count: 2

        // offset: 1, node->slot:[1]: kmem_cache#20-o0(RADIX_LSB:0)->slots[1], item: kmem_cache#28-o1 (irq: 1)
		rcu_assign_pointer(node->slots[offset], item);
		// kmem_cache#20-o0(RADIX_LSB:0)->slots[1]: kmem_cache#28-o1 (irq: 1)

        // node: 
		BUG_ON(tag_get(node, 0, offset));
		BUG_ON(tag_get(node, 1, offset));
	} else {
...
    }

	return 0;
}
EXPORT_SYMBOL(radix_tree_insert);

radix-tree.c::tag_get()

static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
		int offset)
{
	return test_bit(offset, node->tags[tag]);
}

non_atomic.h::test_bit()

static inline int test_bit(int nr, const volatile unsigned long *addr)
{
	// nr: 0, BIT_WORD(0): 0, addr[0]: cpu_possible_mask->bits[0]: 0xF
	return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
	// return 1 & (0xF >> 0): 1
}

return 0

radix-tree.c::tag_get()

node, 1, offset

static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
		int offset)
{
	return test_bit(offset, node->tags[tag]);
}

non_atomic.h::test_bit()

static inline int test_bit(int nr, const volatile unsigned long *addr)
{
	// nr: 0, BIT_WORD(0): 0, addr[0]: cpu_possible_mask->bits[0]: 0xF
	return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
	// return 1 & (0xF >> 0): 1
}

return 0

git log

1st log

   fcb91c0..bc072d1  master     -> origin/master
Updating fcb91c0..bc072d1
Fast-forward
arch/arm/include/asm/bitops.h         |  6 ++++++
arch/arm/lib/findbit.S                |  4 ++++
drivers/irqchip/irq-gic.c             | 12 ++++++++++++
include/asm-generic/bitsperlong.h     |  4 +++-
include/linux/bitmap.h                |  2 ++
include/linux/bitops.h                |  2 ++
include/linux/export.h                |  3 +++
include/linux/irq.h                   |  3 +++
include/linux/irqdesc.h               |  1 +
include/linux/topology.h              |  1 +
include/uapi/asm-generic/errno-base.h |  2 ++
kernel/irq/internals.h                |  1 +
kernel/irq/irqdesc.c                  | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/bitmap.c                          | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++
14 files changed, 169 insertions(+), 1 deletion(-)

2nd log

   bc072d1..01c08ee  master     -> origin/master
Updating bc072d1..01c08ee
Fast-forward
include/asm-generic/bitops/non-atomic.h |   2 +
include/linux/gfp.h                     |   4 ++
include/linux/preempt_mask.h            |   1 +
include/linux/radix-tree.h              |  10 ++++
include/linux/rcupdate.h                |  22 ++++++++-
kernel/irq/irqdesc.c                    |  69 +++++++++++++++++++++++++++-
lib/radix-tree.c                        | 328 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
mm/slub.c                               |   2 +
8 files changed, 435 insertions(+), 3 deletions(-)

3th log

    01c08ee..a82b8aa  master     -> origin/master
Updating 01c08ee..a82b8aa
Fast-forward
include/asm-generic/bitsperlong.h |  2 ++
kernel/irq/irqdesc.c              | 12 ++++++------
2 files changed, 8 insertions(+), 6 deletions(-)

Files

a10c_78.md

Latest commit

History

a10c_78.md

File metadata and controls

ARM10C 78주차 후기

일시 : 2014.11.15 (78주차)

모임명 : NAVER개발자커뮤니티지원_10차ARM-C

장소 : 토즈 타워점

장소지원 : NAVER 개발자 커뮤니티 지원 프로그램

참여인원 : 3명

진도

main.c::start_kernel()

irq.c::init_IRQ()

irqchip.h::irqchip_init()

irqchip.h::irqchip_init()

irq_gic.c::gic_of_init()

irq-gic.c::gic_init_bases()

irq.h::irq_alloc_descs()

irqdesc.c::__irq_alloc_descs()

bitmap.c::bitmap_find_next_zero_area()

bitops.h::find_next_zero_bit()

findbit.S::_find_next_zero_bit_le()

bitmap.c::bitmap_find_next_zero_area()

bitops.h::find_next_bit()

findbit.S::_find_next_bit_le()

bitmap.c::bitmap_find_next_zero_area()

irqdesc.c::__irq_alloc_descs()

irqdesc.c::irq_expand_nr_irqs()

irqdesc.c::__irq_alloc_descs()

bitmap.c::bitmap_set()

bitops.h::BIT_WORD()

bitmap.c::bitmap_set()

bitmap.h::BITMAP_FIRST_WORD_MASK()

bitmap.c::bitmap_set()

bitmap.c::bitmap_set()

irqdesc.c::__irq_alloc_descs()

irqdesc.c::alloc_descs()

irqdesc.c::irq_insert_desc()

radix-tree.c::radix_tree_insert()

radix-tree.h::radix_tree_is_indirect_ptr()

radix-tree.c::radix_tree_insert()

radix-tree.c::radix_tree_maxindex()

radix-tree.c::indirect_to_ptr()

radix-tree.c::radix_tree_insert()

rcupdate.h::rcu_assign_pointer()

radix-tree.c::radix_tree_insert()

radix-tree.c::root_tag_get()

radix-tree.c::root_tag_get()

radix-tree.c::radix_tree_insert()

radix-tree.c::radix_tree_insert()

radix-tree.c::radix_tree_extend()

radix-tree.c::radix_tree_maxindex()

radix-tree.c::radix_tree_extend()

radix-tree.c::radix_tree_node_alloc()

radix-tree.c::root_gfp_mask()

radix-tree.c::radix_tree_node_alloc()

radix-tree.c::radix_tree_extend()

radix-reee.c::ptr_to_indirect()

radix-tree.c::radix_tree_extend()

radix-tree.c::radix_tree_insert()

radix-tree.c::tag_get()

non_atomic.h::test_bit()

radix-tree.c::tag_get()

non_atomic.h::test_bit()

git log