add list_del_head[_init] functions

PATCH In review Tobias DiPasquale 2 participants 3 messages Nov 27, 2004

Subsystems (8)

Networking Memory management MM core Page allocator +4 more subsystems

lore

Share & tools

lore

Tobias DiPasquale

author

2004-11-27 00:46 UTC #0 lore raw

PATCH 1/1 add list_del_head[_init] functions

Hi all,

I revised my earlier list_del_head patch and took Jens' suggestions. There were two function additions:

list_del_head() - removes the head of a list and returns it list_del_head_init() - removes the head of a list, reinitializes it and returns it

I have also converted several obvious pieces of code in kernel/, net/ and mm/ to use these new functions. The patch for all of this is attached. Thanks :)

Name: Add list_del_head[_init] functions for full queue API
Status: Tested (smoke tests, mostly)

Signed-off-by Toby DiPasquale <[email protected]>

P.S. Again, please CC me on any replies as I'm not subscribed to LKML. Thanks again :)

Signature · 2 lines

[ Tobias DiPasquale ]
0x636f6465736c696e67657240676d61696c2e636f6d

include/linux/list.h +29 -0

diff -Nrup linux-2.6.9/include/linux/list.h linux/include/linux/list.h
@@ -166,6 +166,35 @@ static inline void list_del(struct list_
 }
 
 /**
+ * list_del_head - deletes head entry from list.
+ * @head : list head to delete
+ *
+ * Caller must be sure that the list is not empty before calling 
+ * this function.
+ */
+static inline struct list_head *list_del_head(struct list_head *head)
+{
+	struct list_head *entry = head->next;
+	list_del(head->next);
+	return entry;
+}
+
+/**
+ * list_del_head_init - deletes head entry from list and reinitializes it.
+ * @head : list head to delete
+ *
+ * Caller must be sure that the list is not empty before calling 
+ * this function.
+ */
+static inline struct list_head *list_del_head_init(struct list_head *head)
+{
+	struct list_head *entry = head->next;
+	list_del(head->next);
+	INIT_LIST_HEAD(entry);
+	return entry;
+}
+
+/**
  * list_del_rcu - deletes entry from list without re-initialization
  * @entry: the element to delete from the list.
  *

kernel/audit.c +2 -4

diff -Nrup linux-2.6.9/kernel/audit.c linux/kernel/audit.c
@@ -612,9 +612,8 @@ struct audit_buffer *audit_log_start(str
 
 	spin_lock_irqsave(&audit_freelist_lock, flags);
 	if (!list_empty(&audit_freelist)) {
-		ab = list_entry(audit_freelist.next,
+		ab = list_entry(list_del_head(&audit_freelist),
 				struct audit_buffer, list);
-		list_del(&ab->list);
 		--audit_freelist_count;
 	}
 	spin_unlock_irqrestore(&audit_freelist_lock, flags);

@@ -732,8 +731,7 @@ static void audit_tasklet_handler(unsign
 	spin_unlock_irqrestore(&audit_txlist_lock, flags);
 
 	while (!list_empty(&list)) {
-		ab = list_entry(list.next, struct audit_buffer, list);
-		list_del(&ab->list);
+		ab = list_entry(list_del_head(&list), struct audit_buffer, list);
 		audit_log_end_fast(ab);
 	}
 }

kernel/posix-timers.c +4 -6

diff -Nrup linux-2.6.9/kernel/posix-timers.c linux/kernel/posix-timers.c
@@ -1132,7 +1132,6 @@ retry_delete:
 #else
 	p_timer_del(&posix_clocks[timer->it_clock], timer);
 #endif
-	list_del(&timer->list);
 	/*
 	 * This keeps any tasks waiting on the spin lock from thinking
 	 * they got something (see the lock code above).

@@ -1155,7 +1154,8 @@ void exit_itimers(struct signal_struct *
 	struct k_itimer *tmr;
 
 	while (!list_empty(&sig->posix_timers)) {
-		tmr = list_entry(sig->posix_timers.next, struct k_itimer, list);
+		tmr = list_entry(list_del_head(&sig->posix_timers), 
+				 struct k_itimer, list);
 		itimer_delete(tmr);
 	}
 }

@@ -1369,10 +1369,8 @@ void clock_was_set(void)
 			spin_unlock_irq(&abs_list.lock);
 			break;
 		}
-		timr = list_entry(cws_list.next, struct k_itimer,
-				   abs_timer_entry);
-
-		list_del_init(&timr->abs_timer_entry);
+		timr = list_entry(list_del_head_init(&cws_list), 
+				  struct k_itimer, abs_timer_entry);
 		if (add_clockset_delta(timr, &new_wall_to) &&
 		    del_timer(&timr->it_timer))  /* timer run yet? */
 			add_timer(&timr->it_timer);

kernel/sched.c +1 -2

diff -Nrup linux-2.6.9/kernel/sched.c linux/kernel/sched.c
@@ -4162,10 +4162,9 @@ static int migration_call(struct notifie
 		spin_lock_irq(&rq->lock);
 		while (!list_empty(&rq->migration_queue)) {
 			migration_req_t *req;
-			req = list_entry(rq->migration_queue.next,
+			req = list_entry(list_del_head_init(&rq->migration_queue),
 					 migration_req_t, list);
 			BUG_ON(req->type != REQ_MOVE_TASK);
-			list_del_init(&req->list);
 			complete(&req->done);
 		}
 		spin_unlock_irq(&rq->lock);

kernel/signal.c +2 -2

diff -Nrup linux-2.6.9/kernel/signal.c linux/kernel/signal.c
@@ -296,8 +296,8 @@ static void flush_sigqueue(struct sigpen
 
 	sigemptyset(&queue->signal);
 	while (!list_empty(&queue->list)) {
-		q = list_entry(queue->list.next, struct sigqueue , list);
-		list_del_init(&q->list);
+		q = list_entry(list_del_head_init(&queue->list), 
+			       struct sigqueue, list);
 		__sigqueue_free(q);
 	}
 }

kernel/workqueue.c +4 -5

diff -Nrup linux-2.6.9/kernel/workqueue.c linux/kernel/workqueue.c
@@ -159,12 +159,12 @@ static inline void run_workqueue(struct 
 		dump_stack();
 	}
 	while (!list_empty(&cwq->worklist)) {
-		struct work_struct *work = list_entry(cwq->worklist.next,
-						struct work_struct, entry);
+		struct work_struct *work = 
+			list_entry(list_del_head_init(&cwq->worklist),
+				   struct work_struct, entry);
 		void (*f) (void *) = work->func;
 		void *data = work->data;
 
-		list_del_init(cwq->worklist.next);
 		spin_unlock_irqrestore(&cwq->lock, flags);
 
 		BUG_ON(work->wq_data != cwq);

@@ -457,8 +457,7 @@ static void take_over_work(struct workqu
 
 	while (!list_empty(&list)) {
 		printk("Taking work for %s\n", wq->name);
-		work = list_entry(list.next,struct work_struct,entry);
-		list_del(&work->entry);
+		work = list_entry(list_del_head(&list),struct work_struct,entry);
 		__queue_work(wq->cpu_wq + smp_processor_id(), work);
 	}
 	spin_unlock_irq(&cwq->lock);

mm/highmem.c +1 -2

diff -Nrup linux-2.6.9/mm/highmem.c linux/mm/highmem.c
@@ -557,9 +557,8 @@ void set_page_address(struct page *page,
 		BUG_ON(list_empty(&page_address_pool));
 
 		spin_lock_irqsave(&pool_lock, flags);
-		pam = list_entry(page_address_pool.next,
+		pam = list_entry(list_del_head(&page_address_pool),
 				struct page_address_map, list);
-		list_del(&pam->list);
 		spin_unlock_irqrestore(&pool_lock, flags);
 
 		pam->page = page;

mm/hugetlb.c +1 -2

diff -Nrup linux-2.6.9/mm/hugetlb.c linux/mm/hugetlb.c
@@ -39,9 +39,8 @@ static struct page *dequeue_huge_page(vo
 	}
 	if (nid >= 0 && nid < MAX_NUMNODES &&
 	    !list_empty(&hugepage_freelists[nid])) {
-		page = list_entry(hugepage_freelists[nid].next,
+		page = list_entry(list_del_head(&hugepage_freelists[nid]),
 				  struct page, lru);
-		list_del(&page->lru);
 		free_huge_pages--;
 		free_huge_pages_node[nid]--;
 	}

mm/page_alloc.c +2 -4

diff -Nrup linux-2.6.9/mm/page_alloc.c linux/mm/page_alloc.c
@@ -375,8 +375,7 @@ static struct page *__rmqueue(struct zon
 		if (list_empty(&area->free_list))
 			continue;
 
-		page = list_entry(area->free_list.next, struct page, lru);
-		list_del(&page->lru);
+		page = list_entry(list_del_head(&area->free_list), struct page, lru);
 		index = page - zone->zone_mem_map;
 		if (current_order != MAX_ORDER-1)
 			MARK_USED(index, current_order, area);

@@ -554,8 +553,7 @@ buffered_rmqueue(struct zone *zone, int 
 			pcp->count += rmqueue_bulk(zone, 0,
 						pcp->batch, &pcp->list);
 		if (pcp->count) {
-			page = list_entry(pcp->list.next, struct page, lru);
-			list_del(&page->lru);
+			page = list_entry(list_del_head(&pcp->list), struct page, lru);
 			pcp->count--;
 		}
 		local_irq_restore(flags);

mm/pdflush.c +2 -2

diff -Nrup linux-2.6.9/mm/pdflush.c linux/mm/pdflush.c
@@ -201,8 +201,8 @@ int pdflush_operation(void (*fn)(unsigne
 	} else {
 		struct pdflush_work *pdf;
 
-		pdf = list_entry(pdflush_list.next, struct pdflush_work, list);
-		list_del_init(&pdf->list);
+		pdf = list_entry(list_del_head_init(&pdflush_list), 
+				 struct pdflush_work, list);
 		if (list_empty(&pdflush_list))
 			last_empty_jifs = jiffies;
 		pdf->fn = fn;

mm/swapfile.c +1 -2

diff -Nrup linux-2.6.9/mm/swapfile.c linux/mm/swapfile.c
@@ -890,9 +890,8 @@ static void destroy_swap_extents(struct 
 	while (!list_empty(&sis->extent_list)) {
 		struct swap_extent *se;
 
-		se = list_entry(sis->extent_list.next,
+		se = list_entry(list_del_head(&sis->extent_list),
 				struct swap_extent, list);
-		list_del(&se->list);
 		kfree(se);
 	}
 	sis->nr_extents = 0;

net/core/dev.c +6 -6

diff -Nrup linux-2.6.9/net/core/dev.c linux/net/core/dev.c
@@ -1885,12 +1885,12 @@ static void net_rx_action(struct softirq
 
 		local_irq_enable();
 
-		dev = list_entry(queue->poll_list.next,
-				 struct net_device, poll_list);
+		dev = list_entry(list_del_head_init(&queue->poll_list), 
+				 struct net_device, 
+				 poll_list);
 
 		if (dev->quota <= 0 || dev->poll(dev, &budget)) {
 			local_irq_disable();
-			list_del(&dev->poll_list);
 			list_add_tail(&dev->poll_list, &queue->poll_list);
 			if (dev->quota < 0)
 				dev->quota += dev->weight;

@@ -3009,9 +3009,9 @@ void netdev_run_todo(void)
 	spin_unlock(&net_todo_list_lock);
 		
 	while (!list_empty(&list)) {
-		struct net_device *dev
-			= list_entry(list.next, struct net_device, todo_list);
-		list_del(&dev->todo_list);
+		struct net_device *dev = list_entry(list_del_head(&list), 
+						    struct net_device, 
+						    todo_list);
 
 		switch(dev->reg_state) {
 		case NETREG_REGISTERING:

Arnaldo Carvalho de Melo

2004-11-27 01:16 UTC #1 lore raw

Quoted 13 lines · Tobias DiPasquale

Hi all,
I revised my earlier list_del_head patch and took Jens' suggestions. There were two function additions:
list_del_head() - removes the head of a list and returns it list_del_head_init() - removes the head of a list, reinitializes it and returns it
I have also converted several obvious pieces of code in kernel/, net/ and mm/ to use these new functions. The patch for all of this is attached. Thanks :)

Quoted 7 lines

Name: Add list_del_head[_init] functions for full queue API
Status: Tested (smoke tests, mostly)
Signed-off-by Toby DiPasquale <[email protected]>
P.S. Again, please CC me on any replies as I'm not subscribed to LKML. Thanks again :)

The net_rx_action one doesn't look right.

- Arnaldo