attachment
0001-Ticket-59-Heap-use-after-free-in-ns_job_done.patch

Fixed some logging issues in the code that was missing newlines.
0001-Ticket-59-Heap-use-after-free-in-ns_job_done.2.patch

Fix missing thread check on set data.
0001-Ticket-59-Heap-use-after-free-in-ns_job_done.3.patch

Over all, the patch looks good. Help me understanding some more...

1)
{{{
209 static void
210 work_job_execute(ns_job_t *job)
}}}
PR_ASSERT(job->state == NS_JOB_ARMED); <== Can we assume this?

2) This patch depends upon another patch which is not pushed to master. Could you please give me the pointer to the patch/ticket?
{{{
261 static void
156 262 work_q_wait(ns_thrpool_t *tp)
157 263 {
158 264 PR_Lock(tp->work_q_lock);
}}}

3) This is just from my curiosity... What this min_idle_threads is for? min_something is usually some configured value to specify the lower threshold. This min_idle_threads is dynamically reset with the current lowest value... Is this for statistics or something?
{{{
219 319 if (tp->idle_threads < tp->min_idle_threads) {
220 320 tp->min_idle_threads = tp->idle_threads;
221 321 }
}}}

4) Why doesn't this case need to call event_q_notify(job) even if (job->tp->shutdown == 0)?
{{{
664 if (job->state == NS_JOB_RUNNING && job->work_thread == PR_GetCurrentThread()) {
665 / Just mark it (ie do nothing), the work_job_execute function will trigger internal_ns_job_done /
666 #ifdef DEBUG_FSM
667 ns_log(LOG_DEBUG, "ns_job_done %x tp shutdown -> %x state %d setting to async NS_JOB_NEEDS_DELETE\n", job, job->tp->shutdown, job->state);
668 #endif
669 (void)PR_AtomicSet(&job->state, NS_JOB_NEEDS_DELETE);
}}}

5) Why only these 3 states are allowed to call get_data? Same questions for ns_job_set_data,
{{{
ns_job_get_output_type, ns_job_get_type, ns_job_get_fd?
845 914 ns_job_get_data(ns_job_t *job)
846 915 {
847 916 PR_ASSERT(job);
848 PR_ASSERT(job->state == NS_JOB_WAITING || job->state == NS_JOB_ARMED || job->state == NS_JOB_INITIAL);
917 PR_ASSERT(job->state == NS_JOB_WAITING || job->state == NS_JOB_ARMED || job->state == NS_JOB_RUNNING);
849 918 return job->data;
850 919 }
}}}

6) Persistent means the state RUNNING is never been changed?
{{{
986 } else if ( !NS_JOB_IS_PERSIST(job->job_type) && job->state == NS_JOB_RUNNING && job->work_thread == PR_GetCurrentThread()) {
987 / Just mark it (ie do nothing), the work_job_execute function will trigger internal_ns_job_rearm /
988 #ifdef DEBUG_FSM
989 ns_log(LOG_DEBUG, "ns_rearm_job %x state %d setting NS_JOB_NEEDS_ARM\n", job, job->state);
990 #endif
991 (void)PR_AtomicSet(&job->state, NS_JOB_NEEDS_ARM);
992 return PR_SUCCESS;
993 } else {
}}}
Thanks!

Replying to [comment:1 nhosoi]:

Over all, the patch looks good. Help me understanding some more...

1)
{{{
209 static void
210 work_job_execute(ns_job_t *job)
}}}
PR_ASSERT(job->state == NS_JOB_ARMED); <== Can we assume this?

On which line? To call work_job_execute, it means that either:

• The job is "run now" and is run in the event loop (will be ARMED)
• The job is from an event, and is run in the event loop (also will be ARMED)
• The job is from an event, went to a work_q, and now in a worker (also will be ARMED)

To get to any of the above three, you must move from NEEDS_ARM -> ARMED, so this is a safe assumption.

2) This patch depends upon another patch which is not pushed to master. Could you please give me the pointer to the patch/ticket?
{{{
261 static void
156 262 work_q_wait(ns_thrpool_t *tp)
157 263 {
158 264 PR_Lock(tp->work_q_lock);
}}}

Uhhh no? All of my code is in master except this patch ....

3) This is just from my curiosity... What this min_idle_threads is for? min_something is usually some configured value to specify the lower threshold. This min_idle_threads is dynamically reset with the current lowest value... Is this for statistics or something?
{{{
219 319 if (tp->idle_threads < tp->min_idle_threads) {
220 320 tp->min_idle_threads = tp->idle_threads;
221 321 }
}}}

It's meant to be for thread pool scaling up and down. There is another ticket open #55 to actually make it work. I actually think I would rather just get rid of it, because it's too complicated to implement.

4) Why doesn't this case need to call event_q_notify(job) even if (job->tp->shutdown == 0)?
{{{
664 if (job->state == NS_JOB_RUNNING && job->work_thread == PR_GetCurrentThread()) {
665 / Just mark it (ie do nothing), the work_job_execute function will trigger internal_ns_job_done /
666 #ifdef DEBUG_FSM
667 ns_log(LOG_DEBUG, "ns_job_done %x tp shutdown -> %x state %d setting to async NS_JOB_NEEDS_DELETE\n", job, job->tp->shutdown, job->state);
668 #endif
669 (void)PR_AtomicSet(&job->state, NS_JOB_NEEDS_DELETE);
}}}

Okay, because we are NS_JOB_RUNNING, and work_thread == current thread this means that this happened:

{{{
// some event
work_job_execute(job) {
...
job->func(job)
// mark
}

Which calls the job cb. In that:

cb(job) {
....
ns_job_(done|rearm)(job)
}

Now once the cb is done, we return to work_job_execute at //mark. Then:

work_job_execute(job)
...
//mark
if (state->NEEDS_ARM) {
internal_job_arm ...
} else if (state->NEEDS_DELETE) {
internal_job_done ....
}
}}}

This prevents the race condition with use after free in fact, and is the most important part of patch! It means that a job which is making itself done, doesn't have the data prematurely ripped out from under it. It's only removed "at the completion of the callback". Because it's now in the state NEEDS_ARM or NEEDS_DELETE, no other thread can access or modify it either. Pretty neat, and very safe!

5) Why only these 3 states are allowed to call get_data? Same questions for ns_job_set_data,
{{{
ns_job_get_output_type, ns_job_get_type, ns_job_get_fd?
845 914 ns_job_get_data(ns_job_t *job)
846 915 {
847 916 PR_ASSERT(job);
848 PR_ASSERT(job->state == NS_JOB_WAITING || job->state == NS_JOB_ARMED || job->state == NS_JOB_INITIAL);
917 PR_ASSERT(job->state == NS_JOB_WAITING || job->state == NS_JOB_ARMED || job->state == NS_JOB_RUNNING);
849 918 return job->data;
850 919 }
}}}

Right, so if the job is WAITING, ARMED or RUNNING, it means that the job is either:

• Out of the event or work queue
• It's in the queue, and has been barriered
• It's being acted on by some thread.

If the job is in NEEDS_ARM, it's not behind a memory barrier yet, so we may be reading inconsistent data. If it's in NEEDS_DELETE, it's about to get removed, so we are likely to race to a segfault. Basically, this means that you can only read data from a job, when it's relatively "static", if it's in transition, you can't touch it.

With set data, it is basically the same, but you have to be in WAITING, or RUNNING + current thread. This means that you are the job that is in the callback working on the job, so you can safely modify yourself. Or the job is idle, no one is working on it, and you can safely write to the data. This has some flaws still, but I'm about to open a ticket to fix this on NUMA (nunc-stans is horribly broken on NUMA today)

6) Persistent means the state RUNNING is never been changed?
{{{
986 } else if ( !NS_JOB_IS_PERSIST(job->job_type) && job->state == NS_JOB_RUNNING && job->work_thread == PR_GetCurrentThread()) {
987 / Just mark it (ie do nothing), the work_job_execute function will trigger internal_ns_job_rearm /
988 #ifdef DEBUG_FSM
989 ns_log(LOG_DEBUG, "ns_rearm_job %x state %d setting NS_JOB_NEEDS_ARM\n", job, job->state);
990 #endif
991 (void)PR_AtomicSet(&job->state, NS_JOB_NEEDS_ARM);
992 return PR_SUCCESS;
993 } else {
}}}
Thanks!

If you look at work_job_execute, if the job is persist, as soon as we leave the RUNNING, in work_job_execute, it immediately sends it to NEEDS_ARM. So we don't need to do anything at all. That's why there is specifically an exclusion here on persist jobs, as it's already going to get re-armed correctly at the end of the cb.

Hope that helps!

Replying to [comment:2 firstyear]:

Replying to [comment:1 nhosoi]:

Over all, the patch looks good. Help me understanding some more...

1)
{{{
209 static void
210 work_job_execute(ns_job_t *job)
}}}
PR_ASSERT(job->state == NS_JOB_ARMED); <== Can we assume this?

On which line? To call work_job_execute, it means that either:

• The job is "run now" and is run in the event loop (will be ARMED)
• The job is from an event, and is run in the event loop (also will be ARMED)
• The job is from an event, went to a work_q, and now in a worker (also will be ARMED)

To get to any of the above three, you must move from NEEDS_ARM -> ARMED, so this is a safe assumption.
Sounds good. I just thought you have PR_ASSERT in other function, it'd be safer to have one there in case future modifications are made.

2) This patch depends upon another patch which is not pushed to master. Could you please give me the pointer to the patch/ticket?
{{{
261 static void
156 262 work_q_wait(ns_thrpool_t *tp)
157 263 {
158 264 PR_Lock(tp->work_q_lock);
}}}

Uhhh no? All of my code is in master except this patch ....
Ahhh, sorry! You are right. My mistake... :p

3) This is just from my curiosity... What this min_idle_threads is for? min_something is usually some configured value to specify the lower threshold. This min_idle_threads is dynamically reset with the current lowest value... Is this for statistics or something?
{{{
219 319 if (tp->idle_threads < tp->min_idle_threads) {
220 320 tp->min_idle_threads = tp->idle_threads;
221 321 }
}}}

It's meant to be for thread pool scaling up and down. There is another ticket open #55 to actually make it work. I actually think I would rather just get rid of it, because it's too complicated to implement.
Ah, I see. That makes sense. And if you want to add more tuning parameter, you could do it later. Vote +1 to the simplicity...

4) Why doesn't this case need to call event_q_notify(job) even if (job->tp->shutdown == 0)?
{{{
664 if (job->state == NS_JOB_RUNNING && job->work_thread == PR_GetCurrentThread()) {
665 / Just mark it (ie do nothing), the work_job_execute function will trigger internal_ns_job_done /
666 #ifdef DEBUG_FSM
667 ns_log(LOG_DEBUG, "ns_job_done %x tp shutdown -> %x state %d setting to async NS_JOB_NEEDS_DELETE\n", job, job->tp->shutdown, job->state);
668 #endif
669 (void)PR_AtomicSet(&job->state, NS_JOB_NEEDS_DELETE);
}}}

Okay, because we are NS_JOB_RUNNING, and work_thread == current thread this means that this happened:

{{{
// some event
work_job_execute(job) {
...
job->func(job)
// mark
}

Which calls the job cb. In that:

cb(job) {
....
ns_job_(done|rearm)(job)
}

Now once the cb is done, we return to work_job_execute at //mark. Then:

work_job_execute(job)
...
//mark
if (state->NEEDS_ARM) {
internal_job_arm ...
} else if (state->NEEDS_DELETE) {
internal_job_done ....
}
}}}

This prevents the race condition with use after free in fact, and is the most important part of patch! It means that a job which is making itself done, doesn't have the data prematurely ripped out from under it. It's only removed "at the completion of the callback". Because it's now in the state NEEDS_ARM or NEEDS_DELETE, no other thread can access or modify it either. Pretty neat, and very safe!
Got it. Thanks!

5) Why only these 3 states are allowed to call get_data? Same questions for ns_job_set_data,
{{{
ns_job_get_output_type, ns_job_get_type, ns_job_get_fd?
845 914 ns_job_get_data(ns_job_t *job)
846 915 {
847 916 PR_ASSERT(job);
848 PR_ASSERT(job->state == NS_JOB_WAITING || job->state == NS_JOB_ARMED || job->state == NS_JOB_INITIAL);
917 PR_ASSERT(job->state == NS_JOB_WAITING || job->state == NS_JOB_ARMED || job->state == NS_JOB_RUNNING);
849 918 return job->data;
850 919 }
}}}

Right, so if the job is WAITING, ARMED or RUNNING, it means that the job is either:

• Out of the event or work queue
• It's in the queue, and has been barriered
• It's being acted on by some thread.

If the job is in NEEDS_ARM, it's not behind a memory barrier yet, so we may be reading inconsistent data. If it's in NEEDS_DELETE, it's about to get removed, so we are likely to race to a segfault. Basically, this means that you can only read data from a job, when it's relatively "static", if it's in transition, you can't touch it.
Hmmm, then, you want to just return in such cases instead of calling PR_ASSERT? PR_ASSERT is NOOP in the non-debug build...
{{{

if defined(DEBUG) || defined(FORCE_PR_ASSERT)

#define PR_ASSERT(_expr) \
((_expr)?((void)0):PR_Assert(# _expr,FILE,LINE))
...

else

define PR_ASSERT(expr) ((void) 0)

...

endif

}}}

With set data, it is basically the same, but you have to be in WAITING, or RUNNING + current thread. This means that you are the job that is in the callback working on the job, so you can safely modify yourself. Or the job is idle, no one is working on it, and you can safely write to the data. This has some flaws still, but I'm about to open a ticket to fix this on NUMA (nunc-stans is horribly broken on NUMA today)

6) Persistent means the state RUNNING is never been changed?
{{{
986 } else if ( !NS_JOB_IS_PERSIST(job->job_type) && job->state == NS_JOB_RUNNING && job->work_thread == PR_GetCurrentThread()) {
987 / Just mark it (ie do nothing), the work_job_execute function will trigger internal_ns_job_rearm /
988 #ifdef DEBUG_FSM
989 ns_log(LOG_DEBUG, "ns_rearm_job %x state %d setting NS_JOB_NEEDS_ARM\n", job, job->state);
990 #endif
991 (void)PR_AtomicSet(&job->state, NS_JOB_NEEDS_ARM);
992 return PR_SUCCESS;
993 } else {
}}}
Thanks!

If you look at work_job_execute, if the job is persist, as soon as we leave the RUNNING, in work_job_execute, it immediately sends it to NEEDS_ARM. So we don't need to do anything at all. That's why there is specifically an exclusion here on persist jobs, as it's already going to get re-armed correctly at the end of the cb.

Hope that helps!
Thanks!

Add the extra pr_assert
0001-Ticket-59-Heap-use-after-free-in-ns_job_done.4.patch

Sounds good. I just thought you have PR_ASSERT in other function, it'd be safer to have one there in case future modifications are made.

Added!

It's meant to be for thread pool scaling up and down. There is another ticket open #55 to actually make it work. I actually think I would rather just get rid of it, because it's too complicated to implement.
Ah, I see. That makes sense. And if you want to add more tuning parameter, you could do it later. Vote +1 to the simplicity...

No way. I want to REMOVE the tuning. You say how many threads you want, that's how many you get. None of this "Ohh have this many, and these idle, and up to this". That's complicated as anything. We need to write SAFE code first, not Fast, fancy code.

Anyway, patch for PR_ASSERT on job_armed added.

Replying to [comment:4 firstyear]:

We need to write SAFE code first, not Fast, fancy code.

Anyway, patch for PR_ASSERT on job_armed added.

Ok. You have my ack. For the SAFE code, PR_ASSERT does not look to me a friend of mine since it's not in the released build... It claims it MUST be true, but in the real world, it could get false which is not checked... But I trust your thorough tests.

You are absolutely correct. In a real piece of code, the ASSERT does nothing.

For us for now, we have been building and testing with the ASSERTs so we know that the API can't move into invalid states. However, when some external user attempts to use the library they may hit this problem.

Issue is, to properly express this I probably need to make a breaking change to the API, so I'm thinking for now what is the best way to do it. That way we don't rely on the ASSERTs, and we can still signal to the caller they made a mistake.

commit 309649dc4924bb8f53f9e9016e514f9ca53f9b2a
Writing objects: 100% (8/8), 4.11 KiB | 0 bytes/s, done.
Total 8 (delta 6), reused 0 (delta 0)
To ssh://git.fedorahosted.org/git/nunc-stans.git
a33c41f..309649d master -> master