B-Tree

B+ Tree

The animation simulation

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

An example B+ tree with max degree of 4

 

Unsorted

Find out in UBI system, where doing the write, when data is not FF, it aborts?

http://free-electrons.com/doc/kernel-porting.pdf
get_irqnr_and_base

00691: MACHINE_START(MINI2440, "MINI2440")
00692:  /* Maintainer: Michel Pollet <buserror@gmail.com> */
00693:  .atag_offset = 0x100,
00694:  .map_io  = mini2440_map_io,
00695:  .init_machine = mini2440_init,
00696:  .init_irq = s3c2440_init_irq,
00697:  .init_time = mini2440_init_time,
00698:  .restart = s3c244x_restart,
00699: MACHINE_END

set_handle_irq(s3c24xx_handle_irq);
s3c24xx_handle_irq
  s3c24xx_handle_intc
    irq_find_mapping // getting the irq number
    handle_IRQ(irq, regs);

request_irq

PCI interrupt
http://wiki.osdev.org/Interrupts
http://en.wikipedia.org/wiki/Message_Signaled_Interrupts
http://people.na.infn.it/~garufi/didattica/CorsoAcq/PCI.Local.Bus.Specification.Revision.3.0.pdf
http://www.ics.uci.edu/~harris/ics216/pci/PCI_22.pdf
http://lwn.net/Articles/44139/

Per-CPU variable
http://stackoverflow.com/questions/16978959/how-is-percpu-pointer-implemented-in-kernel

queue_rq, called in __blk_mq_run_hw_queue, blk_mq_make_request

Null Block
default is soft_irq
null_init
  create completion_queue for each CPU.
  initialize the list of the cq.
  null_add_dev

NVMe implementation is using the single queue block layer.

NVMe doorbell
Doorbell[edit]
In a push button analogy applied to computer systems, the term doorbell or doorbell interrupt is often used to describe a mechanism whereby a software system can signal or notify a computer hardware device that there is some work to be done. Typically, the software system will place data in some well known and mutually agreed upon memory location(s), and "ring the doorbell" by writing to a different memory location. This different memory location is often called the doorbell region, and there may even be multiple doorbells serving different purposes in this region. It is this act of writing to the doorbell region of memory that "rings the bell" and notifies the hardware device that the data are ready and waiting. The hardware device would now know that the data are valid and can be acted upon. It would typically write the data to a hard disk drive, or send them over a network, or encrypt them, etc




Kernel Wait Queue
http://linuxinme.blogspot.jp/2007/06/wait-queues.html

How to choose a scheduler for block device
http://lxr.free-electrons.com/ident?i=elevator_init

mg_disk.c

blk_init_queue(mg_request_poll, ...);

mg_request
  mg_issue_req
    mg_out( ... &mg_read_intr)
    mg_do_intr = mg_read_intr


mg_probe
  platform_get_irq
  request_irq(..., mg_irq, ...)

mg_irq
  mg_do_intr //mg_read_intr
    mg_end_request


http://www.ibm.com/developerworks/library/l-timers-list/

work queue

mtd_blkdevs.c is a good example. for use of the delayed queue,

NVMe driver
driver/block/Nvme-core.c
http://www.flashmemorysummit.com/English/Collaterals/Proceedings/2013/20130812_PreConfD_Busch.pdf

Multi Queue Request source code
block/blk-mq.c


PCI
A PCI architecture has no central DMA controller, unlike ISA. Instead, any PCI component can request control of the bus ("become the bus master") and request to read from and write to system memory. More precisely, a PCI component requests bus ownership from the PCI bus controller (usually the southbridge in a modern PC design), which will arbitrate if several devices request bus ownership simultaneously, since there can only be one bus master at one time. When the component is granted ownership, it will issue normal read and write commands on the PCI bus, which will be claimed by the bus controller and will be forwarded to the memory controller using a scheme which is specific to every chipset.

http://xillybus.com/tutorials/pci-express-tlp-pcie-primer-tutorial-guide-1
http://xillybus.com/tutorials/pci-express-tlp-pcie-primer-tutorial-guide-2

http://en.wikipedia.org/wiki/Root_complex



inode and superblock

The superblock is a data structure containing information about the filesystem as a whole. Sometimes the collective data is referred to as filesystem metadata.

This information is sometimes called file metadata (that is, data about the file’s data) and is stored in a separate data structure from the file, called the inode.

The superblock object, which represents a specific mounted filesystem.
The inode object, which represents a specific file.
The dentry object, which represents a directory entry, which is a single component of a path.
The file object, which represents an open file as associated with a process.

irq number and resource registration ...

static struct resource mvsdio_resources[] = {
[0] = {
.start = INTER_REGS_PHYS_BASE + MV_SDMMC_REGS_OFFSET,
.end = INTER_REGS_PHYS_BASE + MV_SDMMC_REGS_OFFSET + SZ_1K -1,
.flags = IORESOURCE_MEM,
},
[1] = {
.start = IRQ_GLOBAL_SDIO,
.end = IRQ_GLOBAL_SDIO,
.flags = IORESOURCE_IRQ,
},
};

#define IRQ_GLOBAL_SDIO 57

Mutual Exclusion in Linux Kernel

Three kinds of Mutual Exclusion:

Mutual exclusion among different process contexts
Semaphore: down, up
Mutex: mutex_lock, mutex_unlock
Preempt disable: preempt_disable, preempt_enable

Mutual exclusion among different interrupt contexts
Hardware interrupt disable: local_irq_disable, local_irq_enable
Software interrupt disable: local_bh_disable, local_bh_enable

Mutual exclusion among different CPUs
Spin lock: spin_lock, spin_unlock
Read write spin lock: write_lock_irq, write_unlock_irq
Atomic operation: atomic_read, atomic_write
Sequence Lock: write_seqlock, write_sequnlock
RCU( Read Copy Update ): rcu_read_lock, rcu_read_unlock
Memory barrier: mb, wmb