Opened 11 months ago

Closed 11 months ago

Last modified 11 months ago

#23157 closed Cleanup/optimization (fixed)

O(n) behaviour in default configuration when uploading many duplicate filenames

Reported by: dw Owned by: timgraham
Component: File uploads/storage Version: master
Severity: Normal Keywords:
Cc: Triage Stage: Accepted
Has patch: yes Needs documentation: no
Needs tests: no Patch needs improvement: yes
Easy pickings: no UI/UX: no

Description

In the default configuration, Django django/core/files/storage.py get_available_name() may degrade to producing a huge number of stat() system calls when a duplicate filename is being uploaded. Since stat() may invoke IO, this may produce a huge data-dependent slowdown that slowly worsens over time.

The problem was originally detected by our test suite, but it is likely that especially older Django installations will be experiencing it too, perhaps without even realizing.

I filed a pull request at https://github.com/django/django/pull/3008 before reading the contributor documentation. It seems to suggest I should file a bug to be triaged before submitting a pull?

This is my first Django contribution, so apologies for any confusion.

Change History (12)

comment:1 Changed 11 months ago by areski

  • Needs documentation unset
  • Needs tests unset
  • Patch needs improvement unset

I tested this PR on master locally and it works nicely for me, the tests run perfectly too

+1 for this contribution

comment:2 Changed 11 months ago by timo

  • Has patch set
  • Triage Stage changed from Unreviewed to Accepted
  • Type changed from Uncategorized to Cleanup/optimization

comment:3 Changed 11 months ago by wkschwartz@…

I'm no expert in security, so forgive me if this is a dumb/naive question, but couldn't this bug be used for DOSing a site? If so, should this patch get a priority/severity upgrade?

comment:4 Changed 11 months ago by aaugustin

Yes, we noticed that possibility as soon as the ticket was filed and we started the private process that we use to deal with security issues. For obvious reasons, we didn't draw attention to this ticket.

In doubt, please disclose possible security issues responsibly, as explained on https://docs.djangoproject.com/en/1.6/internals/security/#reporting-security-issues.

comment:5 Changed 11 months ago by merb

The solution looks clean and simple and the tests working fine.
I would mark it RFC as soon as you fix the PEP8 Error on line 801

comment:6 Changed 11 months ago by merb

  • Triage Stage changed from Accepted to Ready for checkin

lgtm

comment:7 Changed 11 months ago by timgraham

  • Owner changed from nobody to timgraham
  • Patch needs improvement set
  • Status changed from new to assigned
  • Triage Stage changed from Ready for checkin to Accepted

I am working on an alternate patch.

comment:8 Changed 11 months ago by Tim Graham <timograham@…>

  • Resolution set to fixed
  • Status changed from assigned to closed

In dd0c3f4ee1a30c1a1e6055061c6ba6e58c6b54d1:

[1.6.x] Fixed #23157 -- Removed O(n) algorithm when uploading duplicate file names.

This is a security fix. Disclosure following shortly.

comment:9 Changed 11 months ago by Tim Graham <timograham@…>

In 0d8d30b7ddfe83ab03120f4560c7aa153f4d0ed1:

Fixed #23157 -- Removed O(n) algorithm when uploading duplicate file names.

This is a security fix. Disclosure following shortly.

comment:10 Changed 11 months ago by Tim Graham <timograham@…>

In 30042d475bf084c6723c6217a21598d9247a9c41:

[1.4.x] Fixed #23157 -- Removed O(n) algorithm when uploading duplicate file names.

This is a security fix. Disclosure following shortly.

comment:11 Changed 11 months ago by Tim Graham <timograham@…>

In 26cd48e166ac4d84317c8ee6d63ac52a87e8da99:

[1.5.x] Fixed #23157 -- Removed O(n) algorithm when uploading duplicate file names.

This is a security fix. Disclosure following shortly.

comment:12 Changed 11 months ago by Tim Graham <timograham@…>

In 3123f8452cf49071be9110e277eea60ba0032216:

[1.7.x] Fixed #23157 -- Removed O(n) algorithm when uploading duplicate file names.

This is a security fix. Disclosure following shortly.

Note: See TracTickets for help on using tickets.
Back to Top