Windows: Improve locking in threading abstraction
[platform/upstream/libusb.git] / libusb / os / windows_nt_common.c
1 /*
2  * windows backend for libusb 1.0
3  * Copyright © 2009-2012 Pete Batard <pete@akeo.ie>
4  * With contributions from Michael Plante, Orin Eman et al.
5  * Parts of this code adapted from libusb-win32-v1 by Stephan Meyer
6  * HID Reports IOCTLs inspired from HIDAPI by Alan Ott, Signal 11 Software
7  * Hash table functions adapted from glibc, by Ulrich Drepper et al.
8  * Major code testing contribution by Xiaofan Chen
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Lesser General Public
12  * License as published by the Free Software Foundation; either
13  * version 2.1 of the License, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * Lesser General Public License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public
21  * License along with this library; if not, write to the Free Software
22  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23  */
24
25 #include <config.h>
26
27 #include <inttypes.h>
28 #include <process.h>
29 #include <stdio.h>
30
31 #include "libusbi.h"
32 #include "windows_common.h"
33 #include "windows_nt_common.h"
34
35 // Global variables for clock_gettime mechanism
36 static uint64_t hires_ticks_to_ps;
37 static uint64_t hires_frequency;
38
39 #define TIMER_REQUEST_RETRY_MS  100
40 #define WM_TIMER_REQUEST        (WM_USER + 1)
41 #define WM_TIMER_EXIT           (WM_USER + 2)
42
43 // used for monotonic clock_gettime()
44 struct timer_request {
45         struct timespec *tp;
46         HANDLE event;
47 };
48
49 // Timer thread
50 static HANDLE timer_thread = NULL;
51 static DWORD timer_thread_id = 0;
52
53 /* User32 dependencies */
54 DLL_DECLARE_HANDLE(User32);
55 DLL_DECLARE_FUNC_PREFIXED(WINAPI, BOOL, p, GetMessageA, (LPMSG, HWND, UINT, UINT));
56 DLL_DECLARE_FUNC_PREFIXED(WINAPI, BOOL, p, PeekMessageA, (LPMSG, HWND, UINT, UINT, UINT));
57 DLL_DECLARE_FUNC_PREFIXED(WINAPI, BOOL, p, PostThreadMessageA, (DWORD, UINT, WPARAM, LPARAM));
58
59 static unsigned __stdcall windows_clock_gettime_threaded(void *param);
60
61 /*
62 * Converts a windows error to human readable string
63 * uses retval as errorcode, or, if 0, use GetLastError()
64 */
65 #if defined(ENABLE_LOGGING)
66 const char *windows_error_str(DWORD error_code)
67 {
68         static char err_string[ERR_BUFFER_SIZE];
69
70         DWORD size;
71         int len;
72
73         if (error_code == 0)
74                 error_code = GetLastError();
75
76         len = sprintf(err_string, "[%u] ", (unsigned int)error_code);
77
78         // Translate codes returned by SetupAPI. The ones we are dealing with are either
79         // in 0x0000xxxx or 0xE000xxxx and can be distinguished from standard error codes.
80         // See http://msdn.microsoft.com/en-us/library/windows/hardware/ff545011.aspx
81         switch (error_code & 0xE0000000) {
82         case 0:
83                 error_code = HRESULT_FROM_WIN32(error_code); // Still leaves ERROR_SUCCESS unmodified
84                 break;
85         case 0xE0000000:
86                 error_code = 0x80000000 | (FACILITY_SETUPAPI << 16) | (error_code & 0x0000FFFF);
87                 break;
88         default:
89                 break;
90         }
91
92         size = FormatMessageA(FORMAT_MESSAGE_FROM_SYSTEM|FORMAT_MESSAGE_IGNORE_INSERTS,
93                         NULL, error_code, MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
94                         &err_string[len], ERR_BUFFER_SIZE - len, NULL);
95         if (size == 0) {
96                 DWORD format_error = GetLastError();
97                 if (format_error)
98                         snprintf(err_string, ERR_BUFFER_SIZE,
99                                 "Windows error code %u (FormatMessage error code %u)",
100                                 (unsigned int)error_code, (unsigned int)format_error);
101                 else
102                         snprintf(err_string, ERR_BUFFER_SIZE, "Unknown error code %u", (unsigned int)error_code);
103         } else {
104                 // Remove CRLF from end of message, if present
105                 size_t pos = len + size - 2;
106                 if (err_string[pos] == '\r')
107                         err_string[pos] = '\0';
108         }
109
110         return err_string;
111 }
112 #endif
113
114 /* Hash table functions - modified From glibc 2.3.2:
115    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
116    [Knuth]            The Art of Computer Programming, part 3 (6.4)  */
117
118 #define HTAB_SIZE 1021UL        // *MUST* be a prime number!!
119
120 typedef struct htab_entry {
121         unsigned long used;
122         char *str;
123 } htab_entry;
124
125 static htab_entry *htab_table = NULL;
126 static usbi_mutex_t htab_mutex;
127 static unsigned long htab_filled;
128
129 /* Before using the hash table we must allocate memory for it.
130    We allocate one element more as the found prime number says.
131    This is done for more effective indexing as explained in the
132    comment for the hash function.  */
133 static bool htab_create(struct libusb_context *ctx)
134 {
135         if (htab_table != NULL) {
136                 usbi_err(ctx, "hash table already allocated");
137                 return true;
138         }
139
140         // Create a mutex
141         usbi_mutex_init(&htab_mutex);
142
143         usbi_dbg("using %lu entries hash table", HTAB_SIZE);
144         htab_filled = 0;
145
146         // allocate memory and zero out.
147         htab_table = calloc(HTAB_SIZE + 1, sizeof(htab_entry));
148         if (htab_table == NULL) {
149                 usbi_err(ctx, "could not allocate space for hash table");
150                 return false;
151         }
152
153         return true;
154 }
155
156 /* After using the hash table it has to be destroyed.  */
157 static void htab_destroy(void)
158 {
159         unsigned long i;
160
161         if (htab_table == NULL)
162                 return;
163
164         for (i = 0; i < HTAB_SIZE; i++)
165                 free(htab_table[i].str);
166
167         safe_free(htab_table);
168
169         usbi_mutex_destroy(&htab_mutex);
170 }
171
172 /* This is the search function. It uses double hashing with open addressing.
173    We use a trick to speed up the lookup. The table is created with one
174    more element available. This enables us to use the index zero special.
175    This index will never be used because we store the first hash index in
176    the field used where zero means not used. Every other value means used.
177    The used field can be used as a first fast comparison for equality of
178    the stored and the parameter value. This helps to prevent unnecessary
179    expensive calls of strcmp.  */
180 unsigned long htab_hash(const char *str)
181 {
182         unsigned long hval, hval2;
183         unsigned long idx;
184         unsigned long r = 5381;
185         int c;
186         const char *sz = str;
187
188         if (str == NULL)
189                 return 0;
190
191         // Compute main hash value (algorithm suggested by Nokia)
192         while ((c = *sz++) != 0)
193                 r = ((r << 5) + r) + c;
194         if (r == 0)
195                 ++r;
196
197         // compute table hash: simply take the modulus
198         hval = r % HTAB_SIZE;
199         if (hval == 0)
200                 ++hval;
201
202         // Try the first index
203         idx = hval;
204
205         // Mutually exclusive access (R/W lock would be better)
206         usbi_mutex_lock(&htab_mutex);
207
208         if (htab_table[idx].used) {
209                 if ((htab_table[idx].used == hval) && (strcmp(str, htab_table[idx].str) == 0))
210                         goto out_unlock; // existing hash
211
212                 usbi_dbg("hash collision ('%s' vs '%s')", str, htab_table[idx].str);
213
214                 // Second hash function, as suggested in [Knuth]
215                 hval2 = 1 + hval % (HTAB_SIZE - 2);
216
217                 do {
218                         // Because size is prime this guarantees to step through all available indexes
219                         if (idx <= hval2)
220                                 idx = HTAB_SIZE + idx - hval2;
221                         else
222                                 idx -= hval2;
223
224                         // If we visited all entries leave the loop unsuccessfully
225                         if (idx == hval)
226                                 break;
227
228                         // If entry is found use it.
229                         if ((htab_table[idx].used == hval) && (strcmp(str, htab_table[idx].str) == 0))
230                                 goto out_unlock;
231                 } while (htab_table[idx].used);
232         }
233
234         // Not found => New entry
235
236         // If the table is full return an error
237         if (htab_filled >= HTAB_SIZE) {
238                 usbi_err(NULL, "hash table is full (%lu entries)", HTAB_SIZE);
239                 idx = 0;
240                 goto out_unlock;
241         }
242
243         htab_table[idx].str = _strdup(str);
244         if (htab_table[idx].str == NULL) {
245                 usbi_err(NULL, "could not duplicate string for hash table");
246                 idx = 0;
247                 goto out_unlock;
248         }
249
250         htab_table[idx].used = hval;
251         ++htab_filled;
252
253 out_unlock:
254         usbi_mutex_unlock(&htab_mutex);
255
256         return idx;
257 }
258
259 static int windows_init_dlls(void)
260 {
261         DLL_GET_HANDLE(User32);
262         DLL_LOAD_FUNC_PREFIXED(User32, p, GetMessageA, TRUE);
263         DLL_LOAD_FUNC_PREFIXED(User32, p, PeekMessageA, TRUE);
264         DLL_LOAD_FUNC_PREFIXED(User32, p, PostThreadMessageA, TRUE);
265
266         return LIBUSB_SUCCESS;
267 }
268
269 static void windows_exit_dlls(void)
270 {
271         DLL_FREE_HANDLE(User32);
272 }
273
274 static bool windows_init_clock(struct libusb_context *ctx)
275 {
276         DWORD_PTR affinity, dummy;
277         HANDLE event = NULL;
278         LARGE_INTEGER li_frequency;
279         int i;
280
281         if (QueryPerformanceFrequency(&li_frequency)) {
282                 // Load DLL imports
283                 if (windows_init_dlls() != LIBUSB_SUCCESS) {
284                         usbi_err(ctx, "could not resolve DLL functions");
285                         return false;
286                 }
287
288                 // The hires frequency can go as high as 4 GHz, so we'll use a conversion
289                 // to picoseconds to compute the tv_nsecs part in clock_gettime
290                 hires_frequency = li_frequency.QuadPart;
291                 hires_ticks_to_ps = UINT64_C(1000000000000) / hires_frequency;
292                 usbi_dbg("hires timer available (Frequency: %"PRIu64" Hz)", hires_frequency);
293
294                 // Because QueryPerformanceCounter might report different values when
295                 // running on different cores, we create a separate thread for the timer
296                 // calls, which we glue to the first available core always to prevent timing discrepancies.
297                 if (!GetProcessAffinityMask(GetCurrentProcess(), &affinity, &dummy) || (affinity == 0)) {
298                         usbi_err(ctx, "could not get process affinity: %s", windows_error_str(0));
299                         return false;
300                 }
301
302                 // The process affinity mask is a bitmask where each set bit represents a core on
303                 // which this process is allowed to run, so we find the first set bit
304                 for (i = 0; !(affinity & (DWORD_PTR)(1 << i)); i++);
305                 affinity = (DWORD_PTR)(1 << i);
306
307                 usbi_dbg("timer thread will run on core #%d", i);
308
309                 event = CreateEvent(NULL, FALSE, FALSE, NULL);
310                 if (event == NULL) {
311                         usbi_err(ctx, "could not create event: %s", windows_error_str(0));
312                         return false;
313                 }
314
315                 timer_thread = (HANDLE)_beginthreadex(NULL, 0, windows_clock_gettime_threaded, (void *)event,
316                                 0, (unsigned int *)&timer_thread_id);
317                 if (timer_thread == NULL) {
318                         usbi_err(ctx, "unable to create timer thread - aborting");
319                         CloseHandle(event);
320                         return false;
321                 }
322
323                 if (!SetThreadAffinityMask(timer_thread, affinity))
324                         usbi_warn(ctx, "unable to set timer thread affinity, timer discrepancies may arise");
325
326                 // Wait for timer thread to init before continuing.
327                 if (WaitForSingleObject(event, INFINITE) != WAIT_OBJECT_0) {
328                         usbi_err(ctx, "failed to wait for timer thread to become ready - aborting");
329                         CloseHandle(event);
330                         return false;
331                 }
332
333                 CloseHandle(event);
334         } else {
335                 usbi_dbg("no hires timer available on this platform");
336                 hires_frequency = 0;
337                 hires_ticks_to_ps = UINT64_C(0);
338         }
339
340         return true;
341 }
342
343 void windows_destroy_clock(void)
344 {
345         if (timer_thread) {
346                 // actually the signal to quit the thread.
347                 if (!pPostThreadMessageA(timer_thread_id, WM_TIMER_EXIT, 0, 0)
348                                 || (WaitForSingleObject(timer_thread, INFINITE) != WAIT_OBJECT_0)) {
349                         usbi_dbg("could not wait for timer thread to quit");
350                         TerminateThread(timer_thread, 1);
351                         // shouldn't happen, but we're destroying
352                         // all objects it might have held anyway.
353                 }
354                 CloseHandle(timer_thread);
355                 timer_thread = NULL;
356                 timer_thread_id = 0;
357         }
358 }
359
360 /*
361 * Monotonic and real time functions
362 */
363 static unsigned __stdcall windows_clock_gettime_threaded(void *param)
364 {
365         struct timer_request *request;
366         LARGE_INTEGER hires_counter;
367         MSG msg;
368
369         // The following call will create this thread's message queue
370         // See https://msdn.microsoft.com/en-us/library/windows/desktop/ms644946.aspx
371         pPeekMessageA(&msg, NULL, WM_USER, WM_USER, PM_NOREMOVE);
372
373         // Signal windows_init_clock() that we're ready to service requests
374         if (!SetEvent((HANDLE)param))
375                 usbi_dbg("SetEvent failed for timer init event: %s", windows_error_str(0));
376         param = NULL;
377
378         // Main loop - wait for requests
379         while (1) {
380                 if (pGetMessageA(&msg, NULL, WM_TIMER_REQUEST, WM_TIMER_EXIT) == -1) {
381                         usbi_err(NULL, "GetMessage failed for timer thread: %s", windows_error_str(0));
382                         return 1;
383                 }
384
385                 switch (msg.message) {
386                 case WM_TIMER_REQUEST:
387                         // Requests to this thread are for hires always
388                         // Microsoft says that this function always succeeds on XP and later
389                         // See https://msdn.microsoft.com/en-us/library/windows/desktop/ms644904.aspx
390                         request = (struct timer_request *)msg.lParam;
391                         QueryPerformanceCounter(&hires_counter);
392                         request->tp->tv_sec = (long)(hires_counter.QuadPart / hires_frequency);
393                         request->tp->tv_nsec = (long)(((hires_counter.QuadPart % hires_frequency) / 1000) * hires_ticks_to_ps);
394                         if (!SetEvent(request->event))
395                                 usbi_err(NULL, "SetEvent failed for timer request: %s", windows_error_str(0));
396                         break;
397                 case WM_TIMER_EXIT:
398                         usbi_dbg("timer thread quitting");
399                         return 0;
400                 }
401         }
402 }
403
404 int windows_clock_gettime(int clk_id, struct timespec *tp)
405 {
406         struct timer_request request;
407 #if !defined(_MSC_VER) || (_MSC_VER < 1900)
408         FILETIME filetime;
409         ULARGE_INTEGER rtime;
410 #endif
411         DWORD r;
412
413         switch (clk_id) {
414         case USBI_CLOCK_MONOTONIC:
415                 if (timer_thread) {
416                         request.tp = tp;
417                         request.event = CreateEvent(NULL, FALSE, FALSE, NULL);
418                         if (request.event == NULL)
419                                 return LIBUSB_ERROR_NO_MEM;
420
421                         if (!pPostThreadMessageA(timer_thread_id, WM_TIMER_REQUEST, 0, (LPARAM)&request)) {
422                                 usbi_err(NULL, "PostThreadMessage failed for timer thread: %s", windows_error_str(0));
423                                 CloseHandle(request.event);
424                                 return LIBUSB_ERROR_OTHER;
425                         }
426
427                         do {
428                                 r = WaitForSingleObject(request.event, TIMER_REQUEST_RETRY_MS);
429                                 if (r == WAIT_TIMEOUT)
430                                         usbi_dbg("could not obtain a timer value within reasonable timeframe - too much load?");
431                                 else if (r == WAIT_FAILED)
432                                         usbi_err(NULL, "WaitForSingleObject failed: %s", windows_error_str(0));
433                         } while (r == WAIT_TIMEOUT);
434                         CloseHandle(request.event);
435
436                         if (r == WAIT_OBJECT_0)
437                                 return LIBUSB_SUCCESS;
438                         else
439                                 return LIBUSB_ERROR_OTHER;
440                 }
441                 // Fall through and return real-time if monotonic was not detected @ timer init
442         case USBI_CLOCK_REALTIME:
443 #if defined(_MSC_VER) && (_MSC_VER >= 1900)
444                 timespec_get(tp, TIME_UTC);
445 #else
446                 // We follow http://msdn.microsoft.com/en-us/library/ms724928%28VS.85%29.aspx
447                 // with a predef epoch time to have an epoch that starts at 1970.01.01 00:00
448                 // Note however that our resolution is bounded by the Windows system time
449                 // functions and is at best of the order of 1 ms (or, usually, worse)
450                 GetSystemTimeAsFileTime(&filetime);
451                 rtime.LowPart = filetime.dwLowDateTime;
452                 rtime.HighPart = filetime.dwHighDateTime;
453                 rtime.QuadPart -= EPOCH_TIME;
454                 tp->tv_sec = (long)(rtime.QuadPart / 10000000);
455                 tp->tv_nsec = (long)((rtime.QuadPart % 10000000) * 100);
456 #endif
457                 return LIBUSB_SUCCESS;
458         default:
459                 return LIBUSB_ERROR_INVALID_PARAM;
460         }
461 }
462
463 static void windows_transfer_callback(struct usbi_transfer *itransfer, uint32_t io_result, uint32_t io_size)
464 {
465         int status, istatus;
466
467         usbi_dbg("handling I/O completion with errcode %u, size %u", io_result, io_size);
468
469         switch (io_result) {
470         case NO_ERROR:
471                 status = windows_copy_transfer_data(itransfer, io_size);
472                 break;
473         case ERROR_GEN_FAILURE:
474                 usbi_dbg("detected endpoint stall");
475                 status = LIBUSB_TRANSFER_STALL;
476                 break;
477         case ERROR_SEM_TIMEOUT:
478                 usbi_dbg("detected semaphore timeout");
479                 status = LIBUSB_TRANSFER_TIMED_OUT;
480                 break;
481         case ERROR_OPERATION_ABORTED:
482                 istatus = windows_copy_transfer_data(itransfer, io_size);
483                 if (istatus != LIBUSB_TRANSFER_COMPLETED)
484                         usbi_dbg("Failed to copy partial data in aborted operation: %d", istatus);
485
486                 usbi_dbg("detected operation aborted");
487                 status = LIBUSB_TRANSFER_CANCELLED;
488                 break;
489         default:
490                 usbi_err(ITRANSFER_CTX(itransfer), "detected I/O error %u: %s", io_result, windows_error_str(io_result));
491                 status = LIBUSB_TRANSFER_ERROR;
492                 break;
493         }
494         windows_clear_transfer_priv(itransfer); // Cancel polling
495         if (status == LIBUSB_TRANSFER_CANCELLED)
496                 usbi_handle_transfer_cancellation(itransfer);
497         else
498                 usbi_handle_transfer_completion(itransfer, (enum libusb_transfer_status)status);
499 }
500
501 void windows_handle_callback(struct usbi_transfer *itransfer, uint32_t io_result, uint32_t io_size)
502 {
503         struct libusb_transfer *transfer = USBI_TRANSFER_TO_LIBUSB_TRANSFER(itransfer);
504
505         switch (transfer->type) {
506         case LIBUSB_TRANSFER_TYPE_CONTROL:
507         case LIBUSB_TRANSFER_TYPE_BULK:
508         case LIBUSB_TRANSFER_TYPE_INTERRUPT:
509         case LIBUSB_TRANSFER_TYPE_ISOCHRONOUS:
510                 windows_transfer_callback(itransfer, io_result, io_size);
511                 break;
512         case LIBUSB_TRANSFER_TYPE_BULK_STREAM:
513                 usbi_warn(ITRANSFER_CTX(itransfer), "bulk stream transfers are not yet supported on this platform");
514                 break;
515         default:
516                 usbi_err(ITRANSFER_CTX(itransfer), "unknown endpoint type %d", transfer->type);
517         }
518 }
519
520 int windows_handle_events(struct libusb_context *ctx, struct pollfd *fds, POLL_NFDS_TYPE nfds, int num_ready)
521 {
522         POLL_NFDS_TYPE i;
523         bool found = false;
524         struct usbi_transfer *transfer;
525         struct winfd *pollable_fd = NULL;
526         DWORD io_size, io_result;
527         int r = LIBUSB_SUCCESS;
528
529         usbi_mutex_lock(&ctx->open_devs_lock);
530         for (i = 0; i < nfds && num_ready > 0; i++) {
531
532                 usbi_dbg("checking fd %d with revents = %04x", fds[i].fd, fds[i].revents);
533
534                 if (!fds[i].revents)
535                         continue;
536
537                 num_ready--;
538
539                 // Because a Windows OVERLAPPED is used for poll emulation,
540                 // a pollable fd is created and stored with each transfer
541                 usbi_mutex_lock(&ctx->flying_transfers_lock);
542                 found = false;
543                 list_for_each_entry(transfer, &ctx->flying_transfers, list, struct usbi_transfer) {
544                         pollable_fd = windows_get_fd(transfer);
545                         if (pollable_fd->fd == fds[i].fd) {
546                                 found = true;
547                                 break;
548                         }
549                 }
550                 usbi_mutex_unlock(&ctx->flying_transfers_lock);
551
552                 if (found) {
553                         windows_get_overlapped_result(transfer, pollable_fd, &io_result, &io_size);
554
555                         usbi_remove_pollfd(ctx, pollable_fd->fd);
556                         // let handle_callback free the event using the transfer wfd
557                         // If you don't use the transfer wfd, you run a risk of trying to free a
558                         // newly allocated wfd that took the place of the one from the transfer.
559                         windows_handle_callback(transfer, io_result, io_size);
560                 } else {
561                         usbi_err(ctx, "could not find a matching transfer for fd %d", fds[i]);
562                         r = LIBUSB_ERROR_NOT_FOUND;
563                         break;
564                 }
565         }
566         usbi_mutex_unlock(&ctx->open_devs_lock);
567
568         return r;
569 }
570
571 int windows_common_init(struct libusb_context *ctx)
572 {
573         if (!windows_init_clock(ctx))
574                 goto error_roll_back;
575
576         if (!htab_create(ctx))
577                 goto error_roll_back;
578
579         return LIBUSB_SUCCESS;
580
581 error_roll_back:
582         windows_common_exit();
583         return LIBUSB_ERROR_NO_MEM;
584 }
585
586 void windows_common_exit(void)
587 {
588         htab_destroy();
589         windows_destroy_clock();
590         windows_exit_dlls();
591 }