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

[dw]

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.

[Areski Belaid]

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

+1 for this contribution

[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?

[Aymeric Augustin]

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.

[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

[merb]

lgtm

[Tim Graham]

I am working on an alternate patch.

[Tim Graham <timograham@…>]

In dd0c3f4ee1a30c1a1e6055061c6ba6e58c6b54d1:

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

This is a security fix. Disclosure following shortly.

[Tim Graham <timograham@…>]

In 0d8d30b7ddfe83ab03120f4560c7aa153f4d0ed1:

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

This is a security fix. Disclosure following shortly.

[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.

[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.

[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.