core: Remove use of gettimeofday()
[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 retval)
67 {
68         static char err_string[ERR_BUFFER_SIZE];
69
70         DWORD error_code, format_error;
71         DWORD size;
72         ssize_t i;
73
74         error_code = retval ? retval : GetLastError();
75
76         safe_sprintf(err_string, ERR_BUFFER_SIZE, "[%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, NULL, error_code,
93                         MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT), &err_string[safe_strlen(err_string)],
94                         ERR_BUFFER_SIZE - (DWORD)safe_strlen(err_string), NULL);
95         if (size == 0) {
96                 format_error = GetLastError();
97                 if (format_error)
98                         safe_sprintf(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                         safe_sprintf(err_string, ERR_BUFFER_SIZE, "Unknown error code %u", (unsigned int)error_code);
103         }
104         else {
105                 // Remove CR/LF terminators
106                 for (i = safe_strlen(err_string) - 1; (i >= 0) && ((err_string[i] == 0x0A) || (err_string[i] == 0x0D)); i--)
107                         err_string[i] = 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 1021
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_write_mutex = NULL;
127 static unsigned long htab_size, htab_filled;
128
129 /* For the used double hash method the table size has to be a prime. To
130    correct the user given table size we need a prime test.  This trivial
131    algorithm is adequate because the code is called only during init and
132    the number is likely to be small  */
133 static int isprime(unsigned long number)
134 {
135         // no even number will be passed
136         unsigned int divider = 3;
137
138         while((divider * divider < number) && (number % divider != 0))
139                 divider += 2;
140
141         return (number % divider != 0);
142 }
143
144 /* Before using the hash table we must allocate memory for it.
145    We allocate one element more as the found prime number says.
146    This is done for more effective indexing as explained in the
147    comment for the hash function.  */
148 static bool htab_create(struct libusb_context *ctx, unsigned long nel)
149 {
150         if (htab_table != NULL) {
151                 usbi_err(ctx, "hash table already allocated");
152                 return true;
153         }
154
155         // Create a mutex
156         usbi_mutex_init(&htab_write_mutex);
157
158         // Change nel to the first prime number not smaller as nel.
159         nel |= 1;
160         while (!isprime(nel))
161                 nel += 2;
162
163         htab_size = nel;
164         usbi_dbg("using %lu entries hash table", nel);
165         htab_filled = 0;
166
167         // allocate memory and zero out.
168         htab_table = calloc(htab_size + 1, sizeof(htab_entry));
169         if (htab_table == NULL) {
170                 usbi_err(ctx, "could not allocate space for hash table");
171                 return false;
172         }
173
174         return true;
175 }
176
177 /* After using the hash table it has to be destroyed.  */
178 static void htab_destroy(void)
179 {
180         unsigned long i;
181
182         if (htab_table == NULL)
183                 return;
184
185         for (i = 0; i < htab_size; i++) {
186                 if (htab_table[i].used)
187                         safe_free(htab_table[i].str);
188         }
189
190         usbi_mutex_destroy(&htab_write_mutex);
191         safe_free(htab_table);
192 }
193
194 /* This is the search function. It uses double hashing with open addressing.
195    We use a trick to speed up the lookup. The table is created with one
196    more element available. This enables us to use the index zero special.
197    This index will never be used because we store the first hash index in
198    the field used where zero means not used. Every other value means used.
199    The used field can be used as a first fast comparison for equality of
200    the stored and the parameter value. This helps to prevent unnecessary
201    expensive calls of strcmp.  */
202 unsigned long htab_hash(const char *str)
203 {
204         unsigned long hval, hval2;
205         unsigned long idx;
206         unsigned long r = 5381;
207         int c;
208         const char *sz = str;
209
210         if (str == NULL)
211                 return 0;
212
213         // Compute main hash value (algorithm suggested by Nokia)
214         while ((c = *sz++) != 0)
215                 r = ((r << 5) + r) + c;
216         if (r == 0)
217                 ++r;
218
219         // compute table hash: simply take the modulus
220         hval = r % htab_size;
221         if (hval == 0)
222                 ++hval;
223
224         // Try the first index
225         idx = hval;
226
227         if (htab_table[idx].used) {
228                 if ((htab_table[idx].used == hval) && (safe_strcmp(str, htab_table[idx].str) == 0))
229                         return idx; // existing hash
230
231                 usbi_dbg("hash collision ('%s' vs '%s')", str, htab_table[idx].str);
232
233                 // Second hash function, as suggested in [Knuth]
234                 hval2 = 1 + hval % (htab_size - 2);
235
236                 do {
237                         // Because size is prime this guarantees to step through all available indexes
238                         if (idx <= hval2)
239                                 idx = htab_size + idx - hval2;
240                         else
241                                 idx -= hval2;
242
243                         // If we visited all entries leave the loop unsuccessfully
244                         if (idx == hval)
245                                 break;
246
247                         // If entry is found use it.
248                         if ((htab_table[idx].used == hval) && (safe_strcmp(str, htab_table[idx].str) == 0))
249                                 return idx;
250                 } while (htab_table[idx].used);
251         }
252
253         // Not found => New entry
254
255         // If the table is full return an error
256         if (htab_filled >= htab_size) {
257                 usbi_err(NULL, "hash table is full (%d entries)", htab_size);
258                 return 0;
259         }
260
261         // Concurrent threads might be storing the same entry at the same time
262         // (eg. "simultaneous" enums from different threads) => use a mutex
263         usbi_mutex_lock(&htab_write_mutex);
264         // Just free any previously allocated string (which should be the same as
265         // new one). The possibility of concurrent threads storing a collision
266         // string (same hash, different string) at the same time is extremely low
267         safe_free(htab_table[idx].str);
268         htab_table[idx].used = hval;
269         htab_table[idx].str = _strdup(str);
270         if (htab_table[idx].str == NULL) {
271                 usbi_err(NULL, "could not duplicate string for hash table");
272                 usbi_mutex_unlock(&htab_write_mutex);
273                 return 0;
274         }
275         ++htab_filled;
276         usbi_mutex_unlock(&htab_write_mutex);
277
278         return idx;
279 }
280
281 static int windows_init_dlls(void)
282 {
283         DLL_GET_HANDLE(User32);
284         DLL_LOAD_FUNC_PREFIXED(User32, p, GetMessageA, TRUE);
285         DLL_LOAD_FUNC_PREFIXED(User32, p, PeekMessageA, TRUE);
286         DLL_LOAD_FUNC_PREFIXED(User32, p, PostThreadMessageA, TRUE);
287
288         return LIBUSB_SUCCESS;
289 }
290
291 static void windows_exit_dlls(void)
292 {
293         DLL_FREE_HANDLE(User32);
294 }
295
296 static bool windows_init_clock(struct libusb_context *ctx)
297 {
298         DWORD_PTR affinity, dummy;
299         HANDLE event = NULL;
300         LARGE_INTEGER li_frequency;
301         int i;
302
303         if (QueryPerformanceFrequency(&li_frequency)) {
304                 // Load DLL imports
305                 if (windows_init_dlls() != LIBUSB_SUCCESS) {
306                         usbi_err(ctx, "could not resolve DLL functions");
307                         return false;
308                 }
309
310                 // The hires frequency can go as high as 4 GHz, so we'll use a conversion
311                 // to picoseconds to compute the tv_nsecs part in clock_gettime
312                 hires_frequency = li_frequency.QuadPart;
313                 hires_ticks_to_ps = UINT64_C(1000000000000) / hires_frequency;
314                 usbi_dbg("hires timer available (Frequency: %"PRIu64" Hz)", hires_frequency);
315
316                 // Because QueryPerformanceCounter might report different values when
317                 // running on different cores, we create a separate thread for the timer
318                 // calls, which we glue to the first available core always to prevent timing discrepancies.
319                 if (!GetProcessAffinityMask(GetCurrentProcess(), &affinity, &dummy) || (affinity == 0)) {
320                         usbi_err(ctx, "could not get process affinity: %s", windows_error_str(0));
321                         return false;
322                 }
323
324                 // The process affinity mask is a bitmask where each set bit represents a core on
325                 // which this process is allowed to run, so we find the first set bit
326                 for (i = 0; !(affinity & (DWORD_PTR)(1 << i)); i++);
327                 affinity = (DWORD_PTR)(1 << i);
328
329                 usbi_dbg("timer thread will run on core #%d", i);
330
331                 event = CreateEvent(NULL, FALSE, FALSE, NULL);
332                 if (event == NULL) {
333                         usbi_err(ctx, "could not create event: %s", windows_error_str(0));
334                         return false;
335                 }
336
337                 timer_thread = (HANDLE)_beginthreadex(NULL, 0, windows_clock_gettime_threaded, (void *)event,
338                                 0, (unsigned int *)&timer_thread_id);
339                 if (timer_thread == NULL) {
340                         usbi_err(ctx, "unable to create timer thread - aborting");
341                         CloseHandle(event);
342                         return false;
343                 }
344
345                 if (!SetThreadAffinityMask(timer_thread, affinity))
346                         usbi_warn(ctx, "unable to set timer thread affinity, timer discrepancies may arise");
347
348                 // Wait for timer thread to init before continuing.
349                 if (WaitForSingleObject(event, INFINITE) != WAIT_OBJECT_0) {
350                         usbi_err(ctx, "failed to wait for timer thread to become ready - aborting");
351                         CloseHandle(event);
352                         return false;
353                 }
354
355                 CloseHandle(event);
356         } else {
357                 usbi_dbg("no hires timer available on this platform");
358                 hires_frequency = 0;
359                 hires_ticks_to_ps = UINT64_C(0);
360         }
361
362         return true;
363 }
364
365 void windows_destroy_clock(void)
366 {
367         if (timer_thread) {
368                 // actually the signal to quit the thread.
369                 if (!pPostThreadMessageA(timer_thread_id, WM_TIMER_EXIT, 0, 0)
370                                 || (WaitForSingleObject(timer_thread, INFINITE) != WAIT_OBJECT_0)) {
371                         usbi_dbg("could not wait for timer thread to quit");
372                         TerminateThread(timer_thread, 1);
373                         // shouldn't happen, but we're destroying
374                         // all objects it might have held anyway.
375                 }
376                 CloseHandle(timer_thread);
377                 timer_thread = NULL;
378                 timer_thread_id = 0;
379         }
380 }
381
382 /*
383 * Monotonic and real time functions
384 */
385 static unsigned __stdcall windows_clock_gettime_threaded(void *param)
386 {
387         struct timer_request *request;
388         LARGE_INTEGER hires_counter;
389         MSG msg;
390
391         // The following call will create this thread's message queue
392         // See https://msdn.microsoft.com/en-us/library/windows/desktop/ms644946.aspx
393         pPeekMessageA(&msg, NULL, WM_USER, WM_USER, PM_NOREMOVE);
394
395         // Signal windows_init_clock() that we're ready to service requests
396         if (!SetEvent((HANDLE)param))
397                 usbi_dbg("SetEvent failed for timer init event: %s", windows_error_str(0));
398         param = NULL;
399
400         // Main loop - wait for requests
401         while (1) {
402                 if (pGetMessageA(&msg, NULL, WM_TIMER_REQUEST, WM_TIMER_EXIT) == -1) {
403                         usbi_err(NULL, "GetMessage failed for timer thread: %s", windows_error_str(0));
404                         return 1;
405                 }
406
407                 switch (msg.message) {
408                 case WM_TIMER_REQUEST:
409                         // Requests to this thread are for hires always
410                         // Microsoft says that this function always succeeds on XP and later
411                         // See https://msdn.microsoft.com/en-us/library/windows/desktop/ms644904.aspx
412                         request = (struct timer_request *)msg.lParam;
413                         QueryPerformanceCounter(&hires_counter);
414                         request->tp->tv_sec = (long)(hires_counter.QuadPart / hires_frequency);
415                         request->tp->tv_nsec = (long)(((hires_counter.QuadPart % hires_frequency) / 1000) * hires_ticks_to_ps);
416                         if (!SetEvent(request->event))
417                                 usbi_err(NULL, "SetEvent failed for timer request: %s", windows_error_str(0));
418                         break;
419                 case WM_TIMER_EXIT:
420                         usbi_dbg("timer thread quitting");
421                         return 0;
422                 }
423         }
424 }
425
426 int windows_clock_gettime(int clk_id, struct timespec *tp)
427 {
428         struct timer_request request;
429 #if !defined(_MSC_VER) || (_MSC_VER < 1900)
430         FILETIME filetime;
431         ULARGE_INTEGER rtime;
432 #endif
433         DWORD r;
434
435         switch (clk_id) {
436         case USBI_CLOCK_MONOTONIC:
437                 if (timer_thread) {
438                         request.tp = tp;
439                         request.event = CreateEvent(NULL, FALSE, FALSE, NULL);
440                         if (request.event == NULL)
441                                 return LIBUSB_ERROR_NO_MEM;
442
443                         if (!pPostThreadMessageA(timer_thread_id, WM_TIMER_REQUEST, 0, (LPARAM)&request)) {
444                                 usbi_err(NULL, "PostThreadMessage failed for timer thread: %s", windows_error_str(0));
445                                 CloseHandle(request.event);
446                                 return LIBUSB_ERROR_OTHER;
447                         }
448
449                         do {
450                                 r = WaitForSingleObject(request.event, TIMER_REQUEST_RETRY_MS);
451                                 if (r == WAIT_TIMEOUT)
452                                         usbi_dbg("could not obtain a timer value within reasonable timeframe - too much load?");
453                                 else if (r == WAIT_FAILED)
454                                         usbi_err(NULL, "WaitForSingleObject failed: %s", windows_error_str(0));
455                         } while (r == WAIT_TIMEOUT);
456                         CloseHandle(request.event);
457
458                         if (r == WAIT_OBJECT_0)
459                                 return LIBUSB_SUCCESS;
460                         else
461                                 return LIBUSB_ERROR_OTHER;
462                 }
463                 // Fall through and return real-time if monotonic was not detected @ timer init
464         case USBI_CLOCK_REALTIME:
465 #if defined(_MSC_VER) && (_MSC_VER >= 1900)
466                 timespec_get(tp, TIME_UTC);
467 #else
468                 // We follow http://msdn.microsoft.com/en-us/library/ms724928%28VS.85%29.aspx
469                 // with a predef epoch time to have an epoch that starts at 1970.01.01 00:00
470                 // Note however that our resolution is bounded by the Windows system time
471                 // functions and is at best of the order of 1 ms (or, usually, worse)
472                 GetSystemTimeAsFileTime(&filetime);
473                 rtime.LowPart = filetime.dwLowDateTime;
474                 rtime.HighPart = filetime.dwHighDateTime;
475                 rtime.QuadPart -= EPOCH_TIME;
476                 tp->tv_sec = (long)(rtime.QuadPart / 10000000);
477                 tp->tv_nsec = (long)((rtime.QuadPart % 10000000) * 100);
478 #endif
479                 return LIBUSB_SUCCESS;
480         default:
481                 return LIBUSB_ERROR_INVALID_PARAM;
482         }
483 }
484
485 static void windows_transfer_callback(struct usbi_transfer *itransfer, uint32_t io_result, uint32_t io_size)
486 {
487         int status, istatus;
488
489         usbi_dbg("handling I/O completion with errcode %u, size %u", io_result, io_size);
490
491         switch (io_result) {
492         case NO_ERROR:
493                 status = windows_copy_transfer_data(itransfer, io_size);
494                 break;
495         case ERROR_GEN_FAILURE:
496                 usbi_dbg("detected endpoint stall");
497                 status = LIBUSB_TRANSFER_STALL;
498                 break;
499         case ERROR_SEM_TIMEOUT:
500                 usbi_dbg("detected semaphore timeout");
501                 status = LIBUSB_TRANSFER_TIMED_OUT;
502                 break;
503         case ERROR_OPERATION_ABORTED:
504                 istatus = windows_copy_transfer_data(itransfer, io_size);
505                 if (istatus != LIBUSB_TRANSFER_COMPLETED)
506                         usbi_dbg("Failed to copy partial data in aborted operation: %d", istatus);
507
508                 usbi_dbg("detected operation aborted");
509                 status = LIBUSB_TRANSFER_CANCELLED;
510                 break;
511         default:
512                 usbi_err(ITRANSFER_CTX(itransfer), "detected I/O error %u: %s", io_result, windows_error_str(io_result));
513                 status = LIBUSB_TRANSFER_ERROR;
514                 break;
515         }
516         windows_clear_transfer_priv(itransfer); // Cancel polling
517         if (status == LIBUSB_TRANSFER_CANCELLED)
518                 usbi_handle_transfer_cancellation(itransfer);
519         else
520                 usbi_handle_transfer_completion(itransfer, (enum libusb_transfer_status)status);
521 }
522
523 void windows_handle_callback(struct usbi_transfer *itransfer, uint32_t io_result, uint32_t io_size)
524 {
525         struct libusb_transfer *transfer = USBI_TRANSFER_TO_LIBUSB_TRANSFER(itransfer);
526
527         switch (transfer->type) {
528         case LIBUSB_TRANSFER_TYPE_CONTROL:
529         case LIBUSB_TRANSFER_TYPE_BULK:
530         case LIBUSB_TRANSFER_TYPE_INTERRUPT:
531         case LIBUSB_TRANSFER_TYPE_ISOCHRONOUS:
532                 windows_transfer_callback(itransfer, io_result, io_size);
533                 break;
534         case LIBUSB_TRANSFER_TYPE_BULK_STREAM:
535                 usbi_warn(ITRANSFER_CTX(itransfer), "bulk stream transfers are not yet supported on this platform");
536                 break;
537         default:
538                 usbi_err(ITRANSFER_CTX(itransfer), "unknown endpoint type %d", transfer->type);
539         }
540 }
541
542 int windows_handle_events(struct libusb_context *ctx, struct pollfd *fds, POLL_NFDS_TYPE nfds, int num_ready)
543 {
544         POLL_NFDS_TYPE i = 0;
545         bool found = false;
546         struct usbi_transfer *transfer;
547         struct winfd *pollable_fd = NULL;
548         DWORD io_size, io_result;
549         int r = LIBUSB_SUCCESS;
550
551         usbi_mutex_lock(&ctx->open_devs_lock);
552         for (i = 0; i < nfds && num_ready > 0; i++) {
553
554                 usbi_dbg("checking fd %d with revents = %04x", fds[i].fd, fds[i].revents);
555
556                 if (!fds[i].revents)
557                         continue;
558
559                 num_ready--;
560
561                 // Because a Windows OVERLAPPED is used for poll emulation,
562                 // a pollable fd is created and stored with each transfer
563                 usbi_mutex_lock(&ctx->flying_transfers_lock);
564                 found = false;
565                 list_for_each_entry(transfer, &ctx->flying_transfers, list, struct usbi_transfer) {
566                         pollable_fd = windows_get_fd(transfer);
567                         if (pollable_fd->fd == fds[i].fd) {
568                                 found = true;
569                                 break;
570                         }
571                 }
572                 usbi_mutex_unlock(&ctx->flying_transfers_lock);
573
574                 if (found) {
575                         windows_get_overlapped_result(transfer, pollable_fd, &io_result, &io_size);
576
577                         usbi_remove_pollfd(ctx, pollable_fd->fd);
578                         // let handle_callback free the event using the transfer wfd
579                         // If you don't use the transfer wfd, you run a risk of trying to free a
580                         // newly allocated wfd that took the place of the one from the transfer.
581                         windows_handle_callback(transfer, io_result, io_size);
582                 } else {
583                         usbi_err(ctx, "could not find a matching transfer for fd %d", fds[i]);
584                         r = LIBUSB_ERROR_NOT_FOUND;
585                         break;
586                 }
587         }
588         usbi_mutex_unlock(&ctx->open_devs_lock);
589
590         return r;
591 }
592
593 int windows_common_init(struct libusb_context *ctx)
594 {
595         if (!windows_init_clock(ctx))
596                 goto error_roll_back;
597
598         if (!htab_create(ctx, HTAB_SIZE))
599                 goto error_roll_back;
600
601         return LIBUSB_SUCCESS;
602
603 error_roll_back:
604         windows_common_exit();
605         return LIBUSB_ERROR_NO_MEM;
606 }
607
608 void windows_common_exit(void)
609 {
610         htab_destroy();
611         windows_destroy_clock();
612         windows_exit_dlls();
613 }