Skip to contentSkip to conversation

RFC: patch to allow lock-free traversal of lists with insertion

Lse-tech Dipankar Sarma 2 participants 3 messages Oct 10, 2001

lore
Share & tools
lore
#0 lore raw
Quoted 5 lines · In article <[email protected]> BALBIR SINGH wrote:

What about cases like the pci device list or any other such list. Sometimes you do not care if somebody added something, while you were looking through the list as long as you do not get illegal addresses or data. Wouldn't this be very useful there? Most of these lists come up at system startup and change rearly, but we look through them often.

How often does the linux kernel need to go through the PCI device list ? Looking at only SCSI code, it seems that not very often. If that is the case in general, optimizing it for lockless lookup (assuming that you use RCU or something to support deletion), is probably an overkill.

One example of where it is useful is maintenance of route information in either storage or network. Route information changes infrequently but needs to be looked up for every I/O and being able to do lockless lookup here is a good gain.

Thanks
Dipankar

Signature · 2 lines
Dipankar Sarma  <[email protected]> Project: http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.
#1 lore raw
Quoted 9 lines · Dipankar Sarma
Quoted 6 lines · In article <[email protected]> BALBIR SINGH wrote:

What about cases like the pci device list or any other such list. Sometimes you do not care if somebody added something, while you were looking through the list as long as you do not get illegal addresses or data. Wouldn't this be very useful there? Most of these lists come up at system startup and change rearly, but we look through them often.

Quoted 6 lines

How often does the linux kernel need to go through the PCI device list ? Looking at only SCSI code, it seems that not very often. If that is the case in general, optimizing it for lockless lookup (assuming that you use RCU or something to support deletion), is probably an overkill.

Almost all pci drivers use the pci_find_slot or some functionality that requires a scan of all the pci devices (to identify their device). I agree that it is not very often.

Quoted 6 lines

One example of where it is useful is maintenance of route information in either storage or network. Route information changes infrequently but needs to be looked up for every I/O and being able to do lockless lookup here is a good gain.

I have a question, can this kind of locking used in cases where an interrupt context may be involved. For example looking through the list of timers, we disable interrupts and grab a lock using spin_lock_irqsave(&timerlist_lock, flags)

Should we just use __cli() with the RCU or something similar? or can RCU be used in such cases?

Thanks,
Balbir

Quoted 5 lines

Thanks
Dipankar

----------------------------------------------------------------------------------------------------------------------
Information transmitted by this E-MAIL is proprietary to Wipro and/or its Customers and is intended for use only by the individual or entity to which it is addressed, and may contain information that is privileged, confidential or exempt from disclosure under applicable law. If you are not the intended recipient or it appears that this mail has been forwarded to you without proper authority, you are notified that any use or dissemination of this information in any manner is strictly prohibited. In such cases, please notify us immediately at mailto:[email protected] and delete this mail from your records.
----------------------------------------------------------------------------------------------------------------------

#2 lore raw
In reply to Dipankar Sarma
Quoted 9 lines · BALBIR SINGH
Quoted 5 lines · Dipankar Sarma

One example of where it is useful is maintenance of route information in either storage or network. Route information changes infrequently but needs to be looked up for every I/O and being able to do lockless lookup here is a good gain.

I have a question, can this kind of locking used in cases where an interrupt context may be involved. For example looking through the list of timers, we disable interrupts and grab a lock using spin_lock_irqsave(&timerlist_lock, flags)

I don't know about this specific case (timer list), but in general, yes, you can use lockless traversal with involvement of interrupt context as long as you can make sure that you see a consistent list if interrupted by the relevant interrupt during any point.

Quoted 3 lines

Should we just use __cli() with the RCU or something similar? or can RCU be used in such cases?

You can use RCU without blocking the relevant interrupt as long as you can make sure that the interrupt cannot find the list in an inconsistent state. For example, if you insert an entry by updating a single "next" pointer, you should be safe. Any interrupt happening before this instruction would see the old copy of data and the ones after the instruction would see the new copy.

As far as deletion using RCU is concerned, it is safe. If you see the old copy of the data in the interrupt handler, that means this CPU was interrupted before the "deletion" was scheduled. If it is the new copy, you don't care.

Thanks
Dipankar

Signature · 2 lines
Dipankar Sarma  <[email protected]> Project: http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.