Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Bug in safe_strtoull affecting use of incr and decr commands #1105

Open
MarkAndreDuesing opened this issue Feb 2, 2024 · 5 comments
Open

Bug in safe_strtoull affecting use of incr and decr commands #1105

MarkAndreDuesing opened this issue Feb 2, 2024 · 5 comments

Comments

@MarkAndreDuesing
Copy link

Describe the bug

There’s a bug in the util.c method safe_strtoull, that causes the commands “incr” and “decr” to work on negative item values.
This section in safe_strtoull:

if ((long long) ull < 0) {
            /* only check for negative signs in the uncommon case when
             * the unsigned number is so big that it's negative as a
             * signed number. */
            if (memchr(str, '-', endptr - str) != NULL) {
                return false;
            }
        }

causes the String that we gave to strtoull to be checked for the minus sign, but only if (long long) ull < 0
Which works fine for any Strings with values between
-1
And
-9223372036854775808 = LONG_MIN

The problem with this is, with String with a value between:
-9223372036854775809 = LONG_MIN-1
And
-18446744073709551615
These will underflow into a positive value when typecast to (long long), causing the memchr check for the minus sign never to be done.
A value in this range is then accepted as safe and used in later methods
(as unsigned long long range values)

The part that leads directly to the error is that they’re use the proto_text.c method
process_arithmetic_command as well as the memcached.c method do_add_delta

This then leads to two kinds of reproducible error:

To Reproduce

One is that the “incr” delta itself can have this error:

> set tok 0 600 3
> 123
< STORED
> incr tok -9912337881327533328
< 8534406192382018411
> get tok
< VALUE tok 0 19
< 8534406192382018411
< END

The second (more likely to actually occur in use) is that the item content value can have this error:

> set tok2 0 600 20
> -9912337881327533328
< STORED
> incr tok2 10
< 8534406192382018298
> get tok2
< VALUE tok2 0 20
< 8534406192382018298 
< END

System Information

  • (Version of)OS/Distro:Ubuntu 22.04.3 LTS
  • Version of memcached: 1.6.22
  • Hardware detail (just running on my Laptop for non-commercial use):
    Hardware Model: Dell Inspiron 5570
    Memory: 8.0 GB
    Processor: Intel Pentium(R) CPU 4415U @ 2.30GHz × 4
    Graphics: Intel HD Graphics 610

Detail (please include!)
Always include the output of stats, stats settings, and optionally stats items and stats slabs. These can be provided to a maintainer privately if necessary. Please sanitize anything secret from the data.

stats
STAT pid 165976
STAT uptime 83
STAT time 1706906444
STAT version 1.6.22
STAT libevent 2.1.12-stable
STAT pointer_size 64
STAT rusage_user 0.024985
STAT rusage_system 0.012492
STAT max_connections 1024
STAT curr_connections 2
STAT total_connections 3
STAT rejected_connections 0
STAT connection_structures 3
STAT response_obj_oom 0
STAT response_obj_count 1
STAT response_obj_bytes 16384
STAT read_buf_count 2
STAT read_buf_bytes 32768
STAT read_buf_bytes_free 0
STAT read_buf_oom 0
STAT reserved_fds 20
STAT cmd_get 2
STAT cmd_set 2
STAT cmd_flush 0
STAT cmd_touch 0
STAT cmd_meta 0
STAT get_hits 2
STAT get_misses 0
STAT get_expired 0
STAT get_flushed 0
STAT delete_misses 0
STAT delete_hits 0
STAT incr_misses 0
STAT incr_hits 2
STAT decr_misses 0
STAT decr_hits 0
STAT cas_misses 0
STAT cas_hits 0
STAT cas_badval 0
STAT touch_hits 0
STAT touch_misses 0
STAT store_too_large 0
STAT store_no_memory 0
STAT auth_cmds 0
STAT auth_errors 0
STAT bytes_read 138
STAT bytes_written 158
STAT limit_maxbytes 67108864
STAT accepting_conns 1
STAT listen_disabled_num 0
STAT time_in_listen_disabled_us 0
STAT threads 4
STAT conn_yields 0
STAT hash_power_level 16
STAT hash_bytes 524288
STAT hash_is_expanding 0
STAT slab_reassign_rescues 0
STAT slab_reassign_chunk_rescues 0
STAT slab_reassign_evictions_nomem 0
STAT slab_reassign_inline_reclaim 0
STAT slab_reassign_busy_items 0
STAT slab_reassign_busy_deletes 0
STAT slab_reassign_running 0
STAT slabs_moved 0
STAT lru_crawler_running 0
STAT lru_crawler_starts 2
STAT lru_maintainer_juggles 197
STAT malloc_fails 0
STAT log_worker_dropped 0
STAT log_worker_written 0
STAT log_watcher_skipped 0
STAT log_watcher_sent 0
STAT log_watchers 0
STAT unexpected_napi_ids 0
STAT round_robin_fallback 0
STAT bytes 164
STAT curr_items 2
STAT total_items 3
STAT slab_global_page_pool 0
STAT expired_unfetched 0
STAT evicted_unfetched 0
STAT evicted_active 0
STAT evictions 0
STAT reclaimed 0
STAT crawler_reclaimed 0
STAT crawler_items_checked 2
STAT lrutail_reflocked 0
STAT moves_to_cold 3
STAT moves_to_warm 0
STAT moves_within_lru 0
STAT direct_reclaims 0
STAT lru_bumps_dropped 0
END
stats settings
STAT maxbytes 67108864
STAT maxconns 1024
STAT tcpport 11111
STAT udpport 0
STAT inter NULL
STAT verbosity 0
STAT oldest 0
STAT evictions on
STAT domain_socket NULL
STAT umask 700
STAT shutdown_command no
STAT growth_factor 1.25
STAT chunk_size 48
STAT num_threads 4
STAT num_threads_per_udp 4
STAT stat_key_prefix :
STAT detail_enabled no
STAT reqs_per_event 20
STAT cas_enabled yes
STAT tcp_backlog 1024
STAT binding_protocol auto-negotiate
STAT auth_enabled_sasl no
STAT auth_enabled_ascii no
STAT item_size_max 1048576
STAT maxconns_fast yes
STAT hashpower_init 0
STAT slab_reassign yes
STAT slab_automove 1
STAT slab_automove_ratio 0.80
STAT slab_automove_window 30
STAT slab_chunk_max 524288
STAT lru_crawler yes
STAT lru_crawler_sleep 100
STAT lru_crawler_tocrawl 0
STAT tail_repair_time 0
STAT flush_enabled yes
STAT dump_enabled yes
STAT hash_algorithm murmur3
STAT lru_maintainer_thread yes
STAT lru_segmented yes
STAT hot_lru_pct 20
STAT warm_lru_pct 40
STAT hot_max_factor 0.20
STAT warm_max_factor 2.00
STAT temp_lru no
STAT temporary_ttl 61
STAT idle_timeout 0
STAT watcher_logbuf_size 262144
STAT worker_logbuf_size 65536
STAT read_buf_mem_limit 0
STAT track_sizes no
STAT inline_ascii_response no
STAT ext_item_size 512
STAT ext_item_age 4294967295
STAT ext_low_ttl 0
STAT ext_recache_rate 2000
STAT ext_wbuf_size 4194304
STAT ext_compact_under 0
STAT ext_drop_under 0
STAT ext_max_sleep 1000000
STAT ext_max_frag 0.80
STAT slab_automove_freeratio 0.010
STAT ext_drop_unread no
STAT num_napi_ids (null)
STAT memory_file (null)
STAT client_flags_size 4
END
stats items
STAT items:1:number 2
STAT items:1:number_hot 0
STAT items:1:number_warm 0
STAT items:1:number_cold 2
STAT items:1:age_hot 0
STAT items:1:age_warm 0
STAT items:1:age 72
STAT items:1:mem_requested 164
STAT items:1:evicted 0
STAT items:1:evicted_nonzero 0
STAT items:1:evicted_time 0
STAT items:1:outofmemory 0
STAT items:1:tailrepairs 0
STAT items:1:reclaimed 0
STAT items:1:expired_unfetched 0
STAT items:1:evicted_unfetched 0
STAT items:1:evicted_active 0
STAT items:1:crawler_reclaimed 0
STAT items:1:crawler_items_checked 2
STAT items:1:lrutail_reflocked 0
STAT items:1:moves_to_cold 3
STAT items:1:moves_to_warm 0
STAT items:1:moves_within_lru 0
STAT items:1:direct_reclaims 0
STAT items:1:hits_to_hot 0
STAT items:1:hits_to_warm 0
STAT items:1:hits_to_cold 2
STAT items:1:hits_to_temp 0
END
stats slabs
STAT 1:chunk_size 96
STAT 1:chunks_per_page 10922
STAT 1:total_pages 1
STAT 1:total_chunks 10922
STAT 1:used_chunks 2
STAT 1:free_chunks 10920
STAT 1:free_chunks_end 0
STAT 1:get_hits 2
STAT 1:cmd_set 2
STAT 1:delete_hits 0
STAT 1:incr_hits 2
STAT 1:decr_hits 0
STAT 1:cas_hits 0
STAT 1:cas_badval 0
STAT 1:touch_hits 0
STAT active_slabs 1
STAT total_malloced 1048576
END
@dormando
Copy link
Member

dormando commented Feb 2, 2024

Thanks! I just fixed a similar bug in there recently. Will see what the deal is.

@dormando
Copy link
Member

(btw, great detail in the bug report here!)

Looks like I don't have a lot of options, either:

  • Remove the negative check and always run memchr
  • skip leading space and check if first character is -

Problem is only a performance consideration. I should be able to benchmark both approaches but it'll take a little more time.

@MarkAndreDuesing
Copy link
Author

Sounds good, thank you. I also couldn't think of an elegant solution that solves the problem without potentially affecting the performance. The benchmarks will be interesting to see.

@dormando
Copy link
Member

I wrote a new tokenizer that I'll be switching to soon (I hope), which removes prefix spaces in the protocol. So at least for strto*'s in the protocol the memchr can be swapped with just checking for - and performance will be less of an issue.

@dormando
Copy link
Member

Just poking an update here. After some major delays due to some other projects running long... I'm on a path to getting this fixed again.

In the new parser code I have custom strto*'s that are much more strict than the builtins: no spaces - must be at the start if signed is allowed, a length must be supplied, and reasonable length limits are enforced (like 11-12 chars for 32-bit numbers, etc). This new parser code will be slow-walked into the codebase after it gets tested out in the proxy code.

This should erase the class of failures where a missing null byte or junk data lets a strto wander off into memory.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@dormando @MarkAndreDuesing