2  like-linux系统下链表结构分析

　　3  *在like-linux系统中，链表的可移植性比较好，并不像在大学学到的链表结构那样的死板。其原理在很多linux的讲解中都有描述。

　　4  *原理部分可以看一下李先静老师写的《系统程序员成长之路》一书。

　　5  *本文根据xenarm中的链表来具体得理一下在like-linux系统中的链表原理。

　　6

　　7  *因为时间有限，只是把相关宏定义简单扩展，并把代码做了注释和筛捡。没有成文，望各位看官见谅

　　8  */

　　9

　　10

　　11 /*

　　12  *定义了一个相关结构和spinlock

　　13  */

　　14 spinlock_t consistent_lock;

　　15 struct arm_vm_region {

　　16         struct list_head        vm_list;

　　17         unsigned long           vm_start;

　　18         unsigned long           vm_end;

　　19         struct page             *vm_pages;

　　20         int                     vm_active;

　　21 };

　　22

　　23 /*

　　24  *初始化一个链表头

　　25  *链表头不同于链表节点，在实际分配中，链表头存放的是边界范围等一些概括信息

　　26  *

　　27  */

　　28 static struct arm_vm_region consistent_head = {//初始化一个链表头

　　29         .vm_list        = LIST_HEAD_INIT(consistent_head.vm_list),

　　30         .vm_start       = CONSISTENT_BASE,

　　31         .vm_end         = CONSISTENT_END,

　　32 };

　　33

　　34 static struct arm_vm_region * arm_vm_region_alloc(struct arm_vm_region *head, size_t size, gfp_t gfp)

　　35 {

　　36         //head头放的是区间总体范围

　　37         unsigned long addr = head->vm_start, end = head->vm_end – size;

　　38         unsigned long flags;

　　39         struct arm_vm_region *c, *new;

　　40

　　41         new = xmalloc(struct arm_vm_region);

　　42         if (!new)

　　43                 goto out;

　　44

　　45         spin_lock_irqsave(&consistent_lock, flags);

　　46

　　47         /*

　　48            *遍历一下链表的各个节点，寻找合适的区间范围

　　49            *list_for_each_entry宏是一个关键，其实是一个for循环，只不过设计的比较巧妙，依靠了链表的结构

　　50            ＊其具体定义在下面

　　51          */

　　52         list_for_each_entry(c, &head->vm_list, vm_list) {

　　53                 if ((addr + size) < addr)//越界

　　54                         goto nospc;

　　55                 if ((addr + size) <= c->vm_start)//可以夹到vm_region块之间

　　56                         goto found;

　　57                 addr = c->vm_end;//addr 为下一个的结束地址

　　58                 if (addr > end)

　　59                         goto nospc;

　　60         }

　　61

　　62  found:

　　63         /*

　　64          * Insert this entry _before_ the one we found.

　　65          */

　　66         list_add_tail(&new->vm_list, &c->vm_list);

　　67         new->vm_start = addr;

　　68         new->vm_end = addr + size;

　　69         new->vm_active = 1;

　　70

　　71         spin_unlock_irqrestore(&consistent_lock, flags);

　　72         return new;

　　73

　　74  nospc:

　　75         spin_unlock_irqrestore(&consistent_lock, flags);

　　76         xfree(new);

　　77  out:

　　78         return NULL;

　　79 }

　　80

　　81 /**

　　82  * list_for_each_entry  -       iterate over list of given type

　　83  * @pos:        the type * to use as a loop counter.

　　84  * @head:       the head for your list.

　　85  * @member:     the name of the list_struct within the struct.

　　86  */

　　87 #define list_for_each_entry(pos, head, member)                          \

　　88         for (pos = list_entry((head)->next, typeof(*pos), member);      \

　　89              &pos->member != (head);                                    \

　　90              pos = list_entry(pos->member.next, typeof(*pos), member))

　　91

　　92 /**

　　93  * list_entry – get the struct for this entry

　　94  * @ptr:        the &struct list_head pointer.

　　95  * @type:       the type of the struct this is embedded in.

　　96  * @member:     the name of the list_struct within the struct.

　　97  */

　　98 #define list_entry(ptr, type, member) \

　　99         ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

　　100 [NextPage]

　　101 /*

　　102    **************************************************

　　103  */

　　104 static void * __dma_alloc(/*struct device *dev,*/size_t size, dma_addr_t *handle/*, gfp_t gfp*/,pgprot_t prot)

　　105 {

　　106         struct page_info *page;

　　107         struct arm_vm_region *c;

　　108         unsigned long order;

　　109         unsigned long flags;

　　110

　　111         //若没有初始化，就…

　　112         if (!consistent_pte[0]) {

　　113                 printk(KERN_ERR "%s: not initialised\n", __func__);

　　114                 return NULL;

　　115         }

　　116         size = round_pgup(size);

　　117

　　118         //若分配的空间太大了，超过了，那么就…

　　119         if (

　　120             size >= (CONSISTENT_END – CONSISTENT_BASE)) {

　　121                 printk(KERN_WARNING "coherent allocation too big "

　　122                        "(requested %#x)\n", size);

　　123                 goto no_page;

　　124         }

　　125

　　126         //转换为伙伴算法的尺寸

　　127         order = get_order_from_bytes(size);

　　128

　　129         local_irq_save(flags);

　　130         page = alloc_heap_pages(0, order);//分配的是实际的页

　　131         local_irq_restore(flags);

　　132         if (!page)

　　133                 goto no_page;

　　134

　　135         c = arm_vm_region_alloc(&consistent_head, size,

　　136                            /* gfp &*/ ~(__GFP_DMA | __GFP_HIGHMEM));//分配的是页框

　　137         if (c) {

　　138                 pte_t *pte;

　　139                 struct page_info *end = page + (1 << order);

　　140                 int idx = CONSISTENT_PTE_INDEX(c->vm_start);

　　141                 u32 off = CONSISTENT_OFFSET(c->vm_start) & (PTRS_PER_PTE-1);

　　142

　　143                 pte = consistent_pte[idx] + off;

　　144                 c->vm_pages = page;

　　145

　　146                 *handle = page_to_phys(page);//page_to_dma(/*dev,*/ page);

　　147

　　148                 do {

　　149                         *pte = l1e_from_paddr(page_to_phys(page), prot);//mk_pte(page, prot);

　　150

　　151                         page++;

　　152                         pte++;

　　153                         off++;

　　154                         if (off >= PTRS_PER_PTE) {

　　155                                 off = 0;

　　156                                 cpu_flush_cache_page((unsigned long)consistent_pte[idx]);

　　157                                 pte = consistent_pte[++idx];

　　158                         }

　　159                 } while (size -= PAGE_SIZE);

　　160                 cpu_flush_cache_page((unsigned long)consistent_pte[idx]);

　　161                 /*

　　162                  * Free the otherwise unused pages.

　　163                  */

　　164                 while (page < end) {//若分配的页数没有全部被映射，于是释放掉没有被映射的页数

　　165                         free_heap_pages(0/*MEMZONE_DMADOM*/,page,order);

　　166                         page++;

　　167                 }

　　168                 return (void *)c->vm_start;

　　169         }

　　170         //如果没有分配vm成功的话，那么就free

　　171         if (page)

　　172                 free_heap_pages(0/*MEMZONE_DMADOM*/,page,order);

　　173  no_page:

　　174         printk("No enough memory for DMA\n");

　　175         *handle = ~0;

　　176         return NULL;

　　177 }

　　178

　　179 pgprot_t pgprot_kernel;

　　180 /*

　　181  * Allocate a writecombining region, in much the same way as

　　182  * dma_alloc_coherent above.

　　183  */

　　184 void *

　　185 dma_alloc_writecombine(/*struct device *dev, */size_t size, dma_addr_t *handle/*, gfp_t gfp*/)

　　186 {

　　187         return __dma_alloc(/*dev, */size, handle, /*gfp,*/

　　188                            pgprot_writecombine(pgprot_kernel));

　　189 }

　　190

　　191 /*

　　192  * Initialise the consistent memory allocation.

　　193  * 先把pgd给初始化了

　　194  */

　　195 int consistent_init(void)

　　196 {

　　197         pde_t *pgd;

　　198         pte_t *pte;

　　199         void *pt;

　　200         int ret = 0, i = 0;

　　201         u32 base = CONSISTENT_BASE;

　　202         pgprot_kernel = PTE_TYPE_SMALL/* | PTE_BUFFERABLE | PTE_CACHEABLE*/ | PTE_SMALL_AP_UNO_SRW;//L_PTE_PRESENT | L_PTE_YOUNG | L_PTE_DIRTY | L_PTE_WRITE | L_PTE_EXEC;

　　203

　　204         do {

　　205                 pt = alloc_xenheap_page();//pte_alloc_kernel(pgd, base);

　　206                 clear_page(pt);

　　207                 idle_pg_table[pgd_index(base)] =l2e_from_page(virt_to_page(pt), PMD_TYPE_TABLE | PMD_DOMAIN(DOMAIN_IO));

　　208                 cpu_flush_cache_page((unsigned long) &idle_pg_table[pgd_index(base)]);

　　209                 if (!pt) {

　　210                         printk(KERN_ERR "%s: no pte tables\n", __func__);

　　211                         ret = -ENOMEM;

　　212                         break;

　　213                 }

　　214                 //这个数组，是为了方便以后分配dma页的时候，建立页表

　　215                 consistent_pte[i++] = pt;

　　216                 base += (1 << PGDIR_SHIFT);

　　217         } while (base < CONSISTENT_END);

　　218         printk("consistent init ok\n");

　　219

　　220         return ret;

　　221 }