What I learned from my first C coding challenge • Hacker News Board

Re: What I learned from my first C coding challenge

#11

Post by twoodfin » Tue, Sep 04, 2012, 7:13 PM UTC

jparishy wrote: post #9

As a note to the author about separating the arrays instead of using a structure, it was probably an alignment issue? Check out http://en.wikipedia.org/wiki/Data_structure_alignment

More specifically, a pointer in x86-64 (and most other 64-bit architectures) is going to be 8-byte aligned, which means that a struct of an 8-byte pointer plus a 2-byte short will actually consume 16 bytes.

Alternatively, keeping them in separate arrays removes the alignment overhead, and each pair of values will consume 10 bytes. That's a substantial savings when you're trying to fit into something like a 32KB L1 data cache.

Another technique that can help you fit as much useful data as possible into L1/L2 cache is to store offsets rather than raw pointers. Using a 2-byte unsigned short for an offset rather than an 8-byte pointer would save another 6 bytes of cache per entry, assuming you're happy limiting your URL size to 64 kilobytes. The extra address arithmetic should be essentially free on a modern pipeline.

Re: What I learned from my first C coding challenge

#12

Post by T-hawk » Tue, Sep 04, 2012, 7:15 PM UTC

jamesaguilar wrote: post #2

I'm trying to picture a non-synthetic program where normalizing a URL is a significant part of the inner loop and I'm drawing a blank. Can someone help me out?

Here's a similar case: Ranking of poker hands. That can involve many of the same steps, like sorting a small list of inputs (5 or 7 cards) into a normalized configuration (three-of-a-kind is represented as AAABC where B > C) and taking a hash to memoize the result. And you sure might want that in a tight inner loop if you're writing a poker simulator or AI where you want to crunch a few billion iterations.

Re: What I learned from my first C coding challenge

#13

Post by jparishy » Tue, Sep 04, 2012, 7:15 PM UTC

twoodfin wrote: post #11

jparishy wrote: post #9

As a note to the author about separating the arrays instead of using a structure, it was probably an alignment issue? Check out http://en.wikipedia.org/wiki/Data_structure_alignment

More specifically, a pointer in x86-64 (and most other 64-bit architectures) is going to be 8-byte aligned, which means that a struct of an 8-byte pointer plus a 2-byte short will actually consume 16 bytes. Alternatively, keeping them in separate arrays removes the alignment overhead, and each pair of values will consume 10 bytes. That's a substantial savings when you're trying to fit into something like a 32KB L1 da…

I was hoping someone would fill in the details; it's been quite a while since I've dealt with anything like that. Thanks!

Re: What I learned from my first C coding challenge

#14

Post by jasonmoo » Tue, Sep 04, 2012, 7:22 PM UTC

twoodfin wrote: post #11

jparishy wrote: post #9

As a note to the author about separating the arrays instead of using a structure, it was probably an alignment issue? Check out http://en.wikipedia.org/wiki/Data_structure_alignment

More specifically, a pointer in x86-64 (and most other 64-bit architectures) is going to be 8-byte aligned, which means that a struct of an 8-byte pointer plus a 2-byte short will actually consume 16 bytes. Alternatively, keeping them in separate arrays removes the alignment overhead, and each pair of values will consume 10 bytes. That's a substantial savings when you're trying to fit into something like a 32KB L1 da…

Thanks guys. This is great info. I messed around with different types for the length value in the struct. Figured something like this was involved.

Re: What I learned from my first C coding challenge

#15

Post by tptacek » Tue, Sep 04, 2012, 7:26 PM UTC

Someone wrote: post #8

tptacek wrote: post #4

Earlier quoted context omitted.

Reading strcmp() makes you think "security hole"? Why?

It does not apply here, but strcmp is, due to the early bailout that any sane implementation uses, suspectible to timing attacks, as in http://www.cs.rice.edu/~scrosby/slides/SCISS-latency.1.ppt .

A timing attack against URL query strings as processed by a normalizing cache proxy?

Re: What I learned from my first C coding challenge

#16

Post by tptacek » Tue, Sep 04, 2012, 7:29 PM UTC

raverbashing wrote: post #10

tptacek wrote: post #4

Earlier quoted context omitted.

Reading strcmp() makes you think "security hole"? Why?

Actually I meant strcpy, but the point stands Point your string function to a non-null terminated byte buffer for example. At the very least you can crash the app What's recommended (one of the recommendations) is to use the 'n' functions like strncmp that takes a maximum size.

I'm sorry, I should have been more direct. No, I meant to say. Using "strcmp" in a typical C program is not a security flaw. It was clear to me you were thinking of "strcat" or "strcpy".

Using strncmp in this situation makes very little sense and is probably more dangerous. The lengths given to strncmp() are inevitably going to be derived from something else that requires a NUL terminator. Meanwhile, strncmp() leaves you open to logic flaws where you compare too few bytes.

Re: What I learned from my first C coding challenge

#17

Post by tptacek » Tue, Sep 04, 2012, 7:29 PM UTC

jparishy wrote: post #6

tptacek wrote: post #4

Earlier quoted context omitted.

Reading strcmp() makes you think "security hole"? Why?

It doesn't take the length/amount of characters to compare as an argument relying on the null terminator, meaning it's susceptible to a buffer overflow attack. Moral of the story, if you're going to use C strings, use the strn* variants.

No, strcmp is not susceptible to buffer overflow attacks.

Re: What I learned from my first C coding challenge

#18

Post by kstop » Tue, Sep 04, 2012, 7:30 PM UTC

We're getting ready to deploy Varnish in (non-devops) work. Not having control over production and having the potential for C inline in the config was already making me a bit nervous. This thread is not helping!

Re: What I learned from my first C coding challenge

#19

Post by masterzora » Tue, Sep 04, 2012, 7:34 PM UTC

tptacek wrote: post #15

Someone wrote: post #8

Earlier quoted context omitted.

It does not apply here, but strcmp is, due to the early bailout that any sane implementation uses, suspectible to timing attacks, as in http://www.cs.rice.edu/~scrosby/slides/SCISS-latency.1.ppt .

A timing attack against URL query strings as processed by a normalizing cache proxy?

Quoth the parent: "It does not apply here"

Re: What I learned from my first C coding challenge

#20

Post by jparishy » Tue, Sep 04, 2012, 7:35 PM UTC

tptacek wrote: post #17

jparishy wrote: post #6

Earlier quoted context omitted.

It doesn't take the length/amount of characters to compare as an argument relying on the null terminator, meaning it's susceptible to a buffer overflow attack. Moral of the story, if you're going to use C strings, use the strn* variants.

No, strcmp is not susceptible to buffer overflow attacks.

https://buildsecurityin.us-cert.gov/bsi-rules/home/g1/847-BS...

If passed an unterminated string, the function will fail at least. How much you could exploit from that, I guess I exaggerated.