Project

General

Profile

Actions

Bug #4840

closed

ddi_dma_mem_alloc()/ddi_dma_mem_free() are O(n**2)

Added by Garrett D'Amore over 8 years ago. Updated over 8 years ago.

Status:
Closed
Priority:
Normal
Category:
kernel
Start date:
2014-05-03
Due date:
% Done:

100%

Estimated time:
Difficulty:
Medium
Tags:
needs-triage
Gerrit CR:

Description

At Pluribus, we found that plumbing additional vnics on ixgbe (with many rings) could take a very long time. Some times plumbing or unplumbing an interface could take over a minute.

Doing some digging, I tracked the problem to kalloca(), kfreea() which use a crummy linked list to track memory allocation sizes. This gets used when the allocations are larger than a page (usually the case with jumbo frames!). In the particular case in question, I found that there were hundreds of thousands of operations being performed to lookup a the size.

Ideally, we would eliminate the need for this record, by having callers keep a record of their allocation to pass with free (like all other kmem users), but I found this to be rather problematic and highly risky to fix (for example, the SCSI tape driver is impacted!)

So, as a low risk interim fix, we are proposing to replace the linked list with an avl tree. We did some tests, and this reduced the run time from many tens of seconds, to a few tens of milliseconds, for this operation. It would be nice to remove even that, but given the risk, it is worthwhile to go ahead with this far lower risk change first.

Note that this problem only affects the x86 platforms.

Actions #1

Updated by Garrett D'Amore over 8 years ago

  • Status changed from New to Resolved

commit a7175e2030b8105e954880bdc63bf0e3dba62d2c
Author: Garrett D'Amore <>
Date: Fri May 2 21:36:57 2014 -0700

4840 ddi_dma_mem_alloc()/ddi_dma_mem_free() are O(n**2)
Reviewed by: Michael Speer &lt;&gt;
Reviewed by: Tycho Nightingale &lt;&gt;
Reviewed by: Rafael Vanoni &lt;&gt;
Reviewed by: Josef 'Jeff' Sipek &lt;&gt;
Reviewed by: Robert Mustacchi &lt;&gt;
Approved by: Dan McDonald &lt;&gt;
Actions #2

Updated by Electric Monk over 8 years ago

  • Status changed from Resolved to Closed
  • % Done changed from 90 to 100
Actions

Also available in: Atom PDF