like-linux系统链表原理简单分析

原创文章,转载请注明出处.转载自: Li Haifeng's Blog
本文链接地址: like-linux系统链表原理简单分析


  1 /*
  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就ok了。
 63          */
 64  found:
 65         /*
 66          * Insert this entry _before_ the one we found.
 67          */
 68         list_add_tail(&new->vm_list, &c->vm_list);
 69         new->vm_start = addr;
 70         new->vm_end = addr + size;
 71         new->vm_active = 1;
 72
 73         spin_unlock_irqrestore(&consistent_lock, flags);
 74         return new;
 75
 76  nospc:
 77         spin_unlock_irqrestore(&consistent_lock, flags);
 78         xfree(new);
 79  out:
 80         return NULL;
 81 }
 82
 83 /**
 84  * list_for_each_entry  –       iterate over list of given type
 85  * @pos:        the type * to use as a loop counter.
 86  * @head:       the head for your list.
 87  * @member:     the name of the list_struct within the struct.
 88  */
 89 #define list_for_each_entry(pos, head, member)                          
 90         for (pos = list_entry((head)->next, typeof(*pos), member);      
 91              &pos->member != (head);                                    
 92              pos = list_entry(pos->member.next, typeof(*pos), member))
 93
 94 /**
 95  * list_entry – get the struct for this entry
 96  * @ptr:        the &struct list_head pointer.
 97  * @type:       the type of the struct this is embedded in.
 98  * @member:     the name of the list_struct within the struct.
 99  */
100 #define list_entry(ptr, type, member)
101         ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
102
103 /*
104    **********************************************************************************************
105  */
106 static void * __dma_alloc(/*struct device *dev,*/size_t size, dma_addr_t *handle/*, gfp_t gfp*/,pgprot_t prot)
107 {
108         struct page_info *page;
109         struct arm_vm_region *c;
110         unsigned long order;
111         unsigned long flags;
112
113         //若没有初始化,就…
114         if (!consistent_pte[0]) {
115                 printk(KERN_ERR "%s: not initialisedn", __func__);
116                 return NULL;
117         }
118         size = round_pgup(size);
119
120         //若分配的空间太大了,超过了,那么就…
121         if (
122             size >= (CONSISTENT_END – CONSISTENT_BASE)) {
123                 printk(KERN_WARNING "coherent allocation too big "
124                        "(requested %#x)n", size);
125                 goto no_page;
126         }
127
128         //转换为伙伴算法的尺寸
129         order = get_order_from_bytes(size);
130
131         local_irq_save(flags);
132         page = alloc_heap_pages(0, order);//分配的是实际的页
133         local_irq_restore(flags);
134         if (!page)
135                 goto no_page;
136
137         c = arm_vm_region_alloc(&consistent_head, size,
138                            /* gfp &*/ ~(__GFP_DMA | __GFP_HIGHMEM));//分配的是页框
139         if (c) {
140                 pte_t *pte;
141                 struct page_info *end = page + (1 << order);
142                 int idx = CONSISTENT_PTE_INDEX(c->vm_start);
143                 u32 off = CONSISTENT_OFFSET(c->vm_start) & (PTRS_PER_PTE-1);
144
145                 pte = consistent_pte[idx] + off;
146                 c->vm_pages = page;
147
148                 *handle = page_to_phys(page);//page_to_dma(/*dev,*/ page);
149
150                 do {
151                         *pte = l1e_from_paddr(page_to_phys(page), prot);//mk_pte(page, prot);
152                         
153                         page++;
154                         pte++;
155                         off++;
156                         if (off >= PTRS_PER_PTE) {
157                                 off = 0;
158                                 cpu_flush_cache_page((unsigned long)consistent_pte[idx]);
159                                 pte = consistent_pte[++idx];
160                         }
161                 } while (size -= PAGE_SIZE);
162                 cpu_flush_cache_page((unsigned long)consistent_pte[idx]);
163                 /*
164                  * Free the otherwise unused pages.
165                  */
166                 while (page < end) {//若分配的页数没有全部被映射,于是释放掉没有被映射的页数
167                         free_heap_pages(0/*MEMZONE_DMADOM*/,page,order);
168                         page++;
169                 }
170                 return (void *)c->vm_start;
171         }
172         //如果没有分配vm成功的话,那么就free
173         if (page)
174                 free_heap_pages(0/*MEMZONE_DMADOM*/,page,order);
175  no_page:
176         printk("No enough memory for DMAn");
177         *handle = ~0;
178         return NULL;
179 }
180
181 pgprot_t pgprot_kernel;
182 /*
183  * Allocate a writecombining region, in much the same way as
184  * dma_alloc_coherent above.
185  */
186 void *
187 dma_alloc_writecombine(/*struct device *dev, */size_t size, dma_addr_t *handle/*, gfp_t gfp*/)
188 {
189         return __dma_alloc(/*dev, */size, handle, /*gfp,*/
190                            pgprot_writecombine(pgprot_kernel));
191 }
192
193 /*
194  * Initialise the consistent memory allocation.
195  * 先把pgd给初始化了
196  */
197 int consistent_init(void)
198 {
199         pde_t *pgd;
200         pte_t *pte;
201         void *pt;
202         int ret = 0, i = 0;
203         u32 base = CONSISTENT_BASE;
204         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;
205
206         do {
207                 pt = alloc_xenheap_page();//pte_alloc_kernel(pgd, base);
208                 clear_page(pt);
209                 idle_pg_table[pgd_index(base)] =l2e_from_page(virt_to_page(pt), PMD_TYPE_TABLE | PMD_DOMAIN(DOMAIN_IO));
210                 cpu_flush_cache_page((unsigned long) &idle_pg_table[pgd_index(base)]);
211                 if (!pt) {
212                         printk(KERN_ERR "%s: no pte tablesn", __func__);
213                         ret = -ENOMEM;
214                         break;
215                 }
216                 //这个数组,是为了方便以后分配dma页的时候,建立页表
217                 consistent_pte[i++] = pt;
218                 base += (1 << PGDIR_SHIFT);
219         } while (base < CONSISTENT_END);
220         printk("consistent init okn");
221
222         return ret;
223 }

From Li Haifeng's Blog, post like-linux系统链表原理简单分析

Post Footer automatically generated by wp-posturl plugin for wordpress.

分享到: