1: /* Provide access to the collection of available transformation modules.
    2:    Copyright (C) 1997-2003, 2004, 2005, 2006, 2007
    3:    Free Software Foundation, Inc.
    4:    This file is part of the GNU C Library.
    5:    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1997.
    6: 
    7:    The GNU C Library is free software; you can redistribute it and/or
    8:    modify it under the terms of the GNU Lesser General Public
    9:    License as published by the Free Software Foundation; either
   10:    version 2.1 of the License, or (at your option) any later version.
   11: 
   12:    The GNU C Library is distributed in the hope that it will be useful,
   13:    but WITHOUT ANY WARRANTY; without even the implied warranty of
   14:    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   15:    Lesser General Public License for more details.
   16: 
   17:    You should have received a copy of the GNU Lesser General Public
   18:    License along with the GNU C Library; if not, write to the Free
   19:    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   20:    02111-1307 USA.  */
   21: 
   22: #include <assert.h>
   23: #include <limits.h>
   24: #include <search.h>
   25: #include <stdlib.h>
   26: #include <string.h>
   27: #include <sys/param.h>
   28: #include <bits/libc-lock.h>
   29: #include <locale/localeinfo.h>
   30: 
   31: #include <dlfcn.h>
   32: #include <gconv_int.h>
   33: #include <sysdep.h>
   34: 
   35: 
   36: /* Simple data structure for alias mapping.  We have two names, `from'
   37:    and `to'.  */
   38: void *__gconv_alias_db;
   39: 
   40: /* Array with available modules.  */
   41: struct gconv_module *__gconv_modules_db;
   42: 
   43: /* We modify global data.   */
   44: __libc_lock_define_initialized (, __gconv_lock)
   45: 
   46: 
   47: /* Provide access to module database.  */
   48: struct gconv_module *
   49: __gconv_get_modules_db (void)
   50: {
   51:   return __gconv_modules_db;
   52: }
   53: 
   54: void *
   55: __gconv_get_alias_db (void)
   56: {
   57:   return __gconv_alias_db;
   58: }
   59: 
   60: 
   61: /* Function for searching alias.  */
   62: int
   63: __gconv_alias_compare (const void *p1, const void *p2)
   64: {
   65:   const struct gconv_alias *s1 = (const struct gconv_alias *) p1;
   66:   const struct gconv_alias *s2 = (const struct gconv_alias *) p2;
   67:   return strcmp (s1->fromname, s2->fromname);
   68: }
   69: 
   70: 
   71: /* To search for a derivation we create a list of intermediate steps.
   72:    Each element contains a pointer to the element which precedes it
   73:    in the derivation order.  */
   74: struct derivation_step
   75: {
   76:   const char *result_set;
   77:   size_t result_set_len;
   78:   int cost_lo;
   79:   int cost_hi;
   80:   struct gconv_module *code;
   81:   struct derivation_step *last;
   82:   struct derivation_step *next;
   83: };
   84: 
   85: #define NEW_STEP(result, hi, lo, module, last_mod) \
   86:   ({ struct derivation_step *newp = alloca (sizeof (struct derivation_step)); \
   87:      newp->result_set = result;                                               \
   88:      newp->result_set_len = strlen (result);                                  \
   89:      newp->cost_hi = hi;                                                      \
   90:      newp->cost_lo = lo;                                                      \
   91:      newp->code = module;                                                     \
   92:      newp->last = last_mod;                                                   \
   93:      newp->next = NULL;                                                       \
   94:      newp; })
   95: 
   96: 
   97: /* If a specific transformation is used more than once we should not need
   98:    to start looking for it again.  Instead cache each successful result.  */
   99: struct known_derivation
  100: {
  101:   const char *from;
  102:   const char *to;
  103:   struct __gconv_step *steps;
  104:   size_t nsteps;
  105: };
  106: 
  107: /* Compare function for database of found derivations.  */
  108: static int
  109: derivation_compare (const void *p1, const void *p2)
  110: {
  111:   const struct known_derivation *s1 = (const struct known_derivation *) p1;
  112:   const struct known_derivation *s2 = (const struct known_derivation *) p2;
  113:   int result;
  114: 
  115:   result = strcmp (s1->from, s2->from);
  116:   if (result == 0)
  117:     result = strcmp (s1->to, s2->to);
  118:   return result;
  119: }
  120: 
  121: /* The search tree for known derivations.  */
  122: static void *known_derivations;
  123: 
  124: /* Look up whether given transformation was already requested before.  */
  125: static int
  126: internal_function
  127: derivation_lookup (const char *fromset, const char *toset,
  128:                    struct __gconv_step **handle, size_t *nsteps)
  129: {
  130:   struct known_derivation key = { fromset, toset, NULL, 0 };
  131:   struct known_derivation **result;
  132: 
  133:   result = __tfind (&key, &known_derivations, derivation_compare);
  134: 
  135:   if (result == NULL)
  136:     return __GCONV_NOCONV;
  137: 
  138:   *handle = (*result)->steps;
  139:   *nsteps = (*result)->nsteps;
  140: 
  141:   /* Please note that we return GCONV_OK even if the last search for
  142:      this transformation was unsuccessful.  */
  143:   return __GCONV_OK;
  144: }
  145: 
  146: /* Add new derivation to list of known ones.  */
  147: static void
  148: internal_function
  149: add_derivation (const char *fromset, const char *toset,
  150:                 struct __gconv_step *handle, size_t nsteps)
  151: {
  152:   struct known_derivation *new_deriv;
  153:   size_t fromset_len = strlen (fromset) + 1;
  154:   size_t toset_len = strlen (toset) + 1;
  155: 
  156:   new_deriv = (struct known_derivation *)
  157:     malloc (sizeof (struct known_derivation) + fromset_len + toset_len);
  158:   if (new_deriv != NULL)
  159:     {
  160:       new_deriv->from = (char *) (new_deriv + 1);
  161:       new_deriv->to = memcpy (__mempcpy (new_deriv + 1, fromset, fromset_len),
  162:                               toset, toset_len);
  163: 
  164:       new_deriv->steps = handle;
  165:       new_deriv->nsteps = nsteps;
  166: 
  167:       if (__tsearch (new_deriv, &known_derivations, derivation_compare)
  168:           == NULL)
  169:         /* There is some kind of memory allocation problem.  */
  170:         free (new_deriv);
  171:     }
  172:   /* Please note that we don't complain if the allocation failed.  This
  173:      is not tragically but in case we use the memory debugging facilities
  174:      not all memory will be freed.  */
  175: }
  176: 
  177: static void __libc_freeres_fn_section
  178: free_derivation (void *p)
  179: {
  180:   struct known_derivation *deriv = (struct known_derivation *) p;
  181:   size_t cnt;
  182: 
  183:   for (cnt = 0; cnt < deriv->nsteps; ++cnt)
  184:     if (deriv->steps[cnt].__counter > 0
  185:         && deriv->steps[cnt].__end_fct != NULL)
  186:       {
  187:         assert (deriv->steps[cnt].__shlib_handle != NULL);
  188: 
  189:         __gconv_end_fct end_fct = deriv->steps[cnt].__end_fct;
  190: #ifdef PTR_DEMANGLE
  191:         PTR_DEMANGLE (end_fct);
  192: #endif
  193:         DL_CALL_FCT (end_fct, (&deriv->steps[cnt]));
  194:       }
  195: 
  196:   /* Free the name strings.  */
  197:   free ((char *) deriv->steps[0].__from_name);
  198:   free ((char *) deriv->steps[deriv->nsteps - 1].__to_name);
  199: 
  200:   free ((struct __gconv_step *) deriv->steps);
  201:   free (deriv);
  202: }
  203: 
  204: 
  205: /* Decrement the reference count for a single step in a steps array.  */
  206: void
  207: internal_function
  208: __gconv_release_step (struct __gconv_step *step)
  209: {
  210:   /* Skip builtin modules; they are not reference counted.  */
  211:   if (step->__shlib_handle != NULL && --step->__counter == 0)
  212:     {
  213:       /* Call the destructor.  */
  214:       if (step->__end_fct != NULL)
  215:         {
  216:           assert (step->__shlib_handle != NULL);
  217: 
  218:           __gconv_end_fct end_fct = step->__end_fct;
  219: #ifdef PTR_DEMANGLE
  220:           PTR_DEMANGLE (end_fct);
  221: #endif
  222:           DL_CALL_FCT (end_fct, (step));
  223:         }
  224: 
  225: #ifndef STATIC_GCONV
  226:       /* Release the loaded module.  */
  227:       __gconv_release_shlib (step->__shlib_handle);
  228:       step->__shlib_handle = NULL;
  229: #endif
  230:     }
  231:   else if (step->__shlib_handle == NULL)
  232:     /* Builtin modules should not have end functions.  */
  233:     assert (step->__end_fct == NULL);
  234: }
  235: 
  236: static int
  237: internal_function
  238: gen_steps (struct derivation_step *best, const char *toset,
  239:            const char *fromset, struct __gconv_step **handle, size_t *nsteps)
  240: {
  241:   size_t step_cnt = 0;
  242:   struct __gconv_step *result;
  243:   struct derivation_step *current;
  244:   int status = __GCONV_NOMEM;
  245: 
  246:   /* First determine number of steps.  */
  247:   for (current = best; current->last != NULL; current = current->last)
  248:     ++step_cnt;
  249: 
  250:   result = (struct __gconv_step *) malloc (sizeof (struct __gconv_step)
  251:                                            * step_cnt);
  252:   if (result != NULL)
  253:     {
  254:       int failed = 0;
  255: 
  256:       status = __GCONV_OK;
  257:       *nsteps = step_cnt;
  258:       current = best;
  259:       while (step_cnt-- > 0)
  260:         {
  261:           result[step_cnt].__from_name = (step_cnt == 0
  262:                                           ? __strdup (fromset)
  263:                                           : (char *)current->last->result_set);
  264:           result[step_cnt].__to_name = (step_cnt + 1 == *nsteps
  265:                                         ? __strdup (current->result_set)
  266:                                         : result[step_cnt + 1].__from_name);
  267: 
  268:           result[step_cnt].__counter = 1;
  269:           result[step_cnt].__data = NULL;
  270: 
  271: #ifndef STATIC_GCONV
  272:           if (current->code->module_name[0] == '/')
  273:             {
  274:               /* Load the module, return handle for it.  */
  275:               struct __gconv_loaded_object *shlib_handle =
  276:                 __gconv_find_shlib (current->code->module_name);
  277: 
  278:               if (shlib_handle == NULL)
  279:                 {
  280:                   failed = 1;
  281:                   break;
  282:                 }
  283: 
  284:               result[step_cnt].__shlib_handle = shlib_handle;
  285:               result[step_cnt].__modname = shlib_handle->name;
  286:               result[step_cnt].__fct = shlib_handle->fct;
  287:               result[step_cnt].__init_fct = shlib_handle->init_fct;
  288:               result[step_cnt].__end_fct = shlib_handle->end_fct;
  289: 
  290:               /* These settings can be overridden by the init function.  */
  291:               result[step_cnt].__btowc_fct = NULL;
  292: 
  293:               /* Call the init function.  */
  294:               __gconv_init_fct init_fct = result[step_cnt].__init_fct;
  295:               if (init_fct != NULL)
  296:                 {
  297:                   assert (result[step_cnt].__shlib_handle != NULL);
  298: 
  299: # ifdef PTR_DEMANGLE
  300:                   PTR_DEMANGLE (init_fct);
  301: # endif
  302:                   status = DL_CALL_FCT (init_fct, (&result[step_cnt]));
  303: 
  304:                   if (__builtin_expect (status, __GCONV_OK) != __GCONV_OK)
  305:                     {
  306:                       failed = 1;
  307:                       /* Make sure we unload this modules.  */
  308:                       --step_cnt;
  309:                       result[step_cnt].__end_fct = NULL;
  310:                       break;
  311:                     }
  312: 
  313: # ifdef PTR_MANGLE
  314:                   if (result[step_cnt].__btowc_fct != NULL)
  315:                     PTR_MANGLE (result[step_cnt].__btowc_fct);
  316: # endif
  317:                 }
  318:             }
  319:           else
  320: #endif
  321:             /* It's a builtin transformation.  */
  322:             __gconv_get_builtin_trans (current->code->module_name,
  323:                                        &result[step_cnt]);
  324: 
  325:           current = current->last;
  326:         }
  327: 
  328:       if (__builtin_expect (failed, 0) != 0)
  329:         {
  330:           /* Something went wrong while initializing the modules.  */
  331:           while (++step_cnt < *nsteps)
  332:             __gconv_release_step (&result[step_cnt]);
  333:           free (result);
  334:           *nsteps = 0;
  335:           *handle = NULL;
  336:           if (status == __GCONV_OK)
  337:             status = __GCONV_NOCONV;
  338:         }
  339:       else
  340:         *handle = result;
  341:     }
  342:   else
  343:     {
  344:       *nsteps = 0;
  345:       *handle = NULL;
  346:     }
  347: 
  348:   return status;
  349: }
  350: 
  351: 
  352: #ifndef STATIC_GCONV
  353: static int
  354: internal_function
  355: increment_counter (struct __gconv_step *steps, size_t nsteps)
  356: {
  357:   /* Increment the user counter.  */
  358:   size_t cnt = nsteps;
  359:   int result = __GCONV_OK;
  360: 
  361:   while (cnt-- > 0)
  362:     {
  363:       struct __gconv_step *step = &steps[cnt];
  364: 
  365:       if (step->__counter++ == 0)
  366:         {
  367:           /* Skip builtin modules.  */
  368:           if (step->__modname != NULL)
  369:             {
  370:               /* Reopen a previously used module.  */
  371:               step->__shlib_handle = __gconv_find_shlib (step->__modname);
  372:               if (step->__shlib_handle == NULL)
  373:                 {
  374:                   /* Oops, this is the second time we use this module
  375:                      (after unloading) and this time loading failed!?  */
  376:                   --step->__counter;
  377:                   while (++cnt < nsteps)
  378:                     __gconv_release_step (&steps[cnt]);
  379:                   result = __GCONV_NOCONV;
  380:                   break;
  381:                 }
  382: 
  383:               /* The function addresses defined by the module may
  384:                  have changed.  */
  385:               step->__fct = step->__shlib_handle->fct;
  386:               step->__init_fct = step->__shlib_handle->init_fct;
  387:               step->__end_fct = step->__shlib_handle->end_fct;
  388: 
  389:               /* These settings can be overridden by the init function.  */
  390:               step->__btowc_fct = NULL;
  391:             }
  392: 
  393:           /* Call the init function.  */
  394:           __gconv_init_fct init_fct = step->__init_fct;
  395:           if (init_fct != NULL)
  396:             {
  397: #ifdef PTR_DEMANGLE
  398:               PTR_DEMANGLE (init_fct);
  399: #endif
  400:               DL_CALL_FCT (init_fct, (step));
  401: 
  402: #ifdef PTR_MANGLE
  403:               if (step->__btowc_fct != NULL)
  404:                 PTR_MANGLE (step->__btowc_fct);
  405: #endif
  406:             }
  407:         }
  408:     }
  409:   return result;
  410: }
  411: #endif
  412: 
  413: 
  414: /* The main function: find a possible derivation from the `fromset' (either
  415:    the given name or the alias) to the `toset' (again with alias).  */
  416: static int
  417: internal_function
  418: find_derivation (const char *toset, const char *toset_expand,
  419:                  const char *fromset, const char *fromset_expand,
  420:                  struct __gconv_step **handle, size_t *nsteps)
  421: {
  422:   struct derivation_step *first, *current, **lastp, *solution = NULL;
  423:   int best_cost_hi = INT_MAX;
  424:   int best_cost_lo = INT_MAX;
  425:   int result;
  426: 
  427:   /* Look whether an earlier call to `find_derivation' has already
  428:      computed a possible derivation.  If so, return it immediately.  */
  429:   result = derivation_lookup (fromset_expand ?: fromset, toset_expand ?: toset,
  430:                               handle, nsteps);
  431:   if (result == __GCONV_OK)
  432:     {
  433: #ifndef STATIC_GCONV
  434:       result = increment_counter (*handle, *nsteps);
  435: #endif
  436:       return result;
  437:     }
  438: 
  439:   /* The task is to find a sequence of transformations, backed by the
  440:      existing modules - whether builtin or dynamically loadable -,
  441:      starting at `fromset' (or `fromset_expand') and ending at `toset'
  442:      (or `toset_expand'), and with minimal cost.
  443: 
  444:      For computer scientists, this is a shortest path search in the
  445:      graph where the nodes are all possible charsets and the edges are
  446:      the transformations listed in __gconv_modules_db.
  447: 
  448:      For now we use a simple algorithm with quadratic runtime behaviour.
  449:      A breadth-first search, starting at `fromset' and `fromset_expand'.
  450:      The list starting at `first' contains all nodes that have been
  451:      visited up to now, in the order in which they have been visited --
  452:      excluding the goal nodes `toset' and `toset_expand' which get
  453:      managed in the list starting at `solution'.
  454:      `current' walks through the list starting at `first' and looks
  455:      which nodes are reachable from the current node, adding them to
  456:      the end of the list [`first' or `solution' respectively] (if
  457:      they are visited the first time) or updating them in place (if
  458:      they have have already been visited).
  459:      In each node of either list, cost_lo and cost_hi contain the
  460:      minimum cost over any paths found up to now, starting at `fromset'
  461:      or `fromset_expand', ending at that node.  best_cost_lo and
  462:      best_cost_hi represent the minimum over the elements of the
  463:      `solution' list.  */
  464: 
  465:   if (fromset_expand != NULL)
  466:     {
  467:       first = NEW_STEP (fromset_expand, 0, 0, NULL, NULL);
  468:       first->next = NEW_STEP (fromset, 0, 0, NULL, NULL);
  469:       lastp = &first->next->next;
  470:     }
  471:   else
  472:     {
  473:       first = NEW_STEP (fromset, 0, 0, NULL, NULL);
  474:       lastp = &first->next;
  475:     }
  476: 
  477:   for (current = first; current != NULL; current = current->next)
  478:     {
  479:       /* Now match all the available module specifications against the
  480:          current charset name.  If any of them matches check whether
  481:          we already have a derivation for this charset.  If yes, use the
  482:          one with the lower costs.  Otherwise add the new charset at the
  483:          end.
  484: 
  485:          The module database is organized in a tree form which allows
  486:          searching for prefixes.  So we search for the first entry with a
  487:          matching prefix and any other matching entry can be found from
  488:          this place.  */
  489:       struct gconv_module *node;
  490: 
  491:       /* Maybe it is not necessary anymore to look for a solution for
  492:          this entry since the cost is already as high (or higher) as
  493:          the cost for the best solution so far.  */
  494:       if (current->cost_hi > best_cost_hi
  495:           || (current->cost_hi == best_cost_hi
  496:               && current->cost_lo >= best_cost_lo))
  497:         continue;
  498: 
  499:       node = __gconv_modules_db;
  500:       while (node != NULL)
  501:         {
  502:           int cmpres = strcmp (current->result_set, node->from_string);
  503:           if (cmpres == 0)
  504:             {
  505:               /* Walk through the list of modules with this prefix and
  506:                  try to match the name.  */
  507:               struct gconv_module *runp;
  508: 
  509:               /* Check all the modules with this prefix.  */
  510:               runp = node;
  511:               do
  512:                 {
  513:                   const char *result_set = (strcmp (runp->to_string, "-") == 0
  514:                                             ? (toset_expand ?: toset)
  515:                                             : runp->to_string);
  516:                   int cost_hi = runp->cost_hi + current->cost_hi;
  517:                   int cost_lo = runp->cost_lo + current->cost_lo;
  518:                   struct derivation_step *step;
  519: 
  520:                   /* We managed to find a derivation.  First see whether
  521:                      we have reached one of the goal nodes.  */
  522:                   if (strcmp (result_set, toset) == 0
  523:                       || (toset_expand != NULL
  524:                           && strcmp (result_set, toset_expand) == 0))
  525:                     {
  526:                       /* Append to the `solution' list if there
  527:                          is no entry with this name.  */
  528:                       for (step = solution; step != NULL; step = step->next)
  529:                         if (strcmp (result_set, step->result_set) == 0)
  530:                           break;
  531: 
  532:                       if (step == NULL)
  533:                         {
  534:                           step = NEW_STEP (result_set,
  535:                                            cost_hi, cost_lo,
  536:                                            runp, current);
  537:                           step->next = solution;
  538:                           solution = step;
  539:                         }
  540:                       else if (step->cost_hi > cost_hi
  541:                                || (step->cost_hi == cost_hi
  542:                                    && step->cost_lo > cost_lo))
  543:                         {
  544:                           /* A better path was found for the node,
  545:                              on the `solution' list.  */
  546:                           step->code = runp;
  547:                           step->last = current;
  548:                           step->cost_hi = cost_hi;
  549:                           step->cost_lo = cost_lo;
  550:                         }
  551: 
  552:                       /* Update best_cost accordingly.  */
  553:                       if (cost_hi < best_cost_hi
  554:                           || (cost_hi == best_cost_hi
  555:                               && cost_lo < best_cost_lo))
  556:                         {
  557:                           best_cost_hi = cost_hi;
  558:                           best_cost_lo = cost_lo;
  559:                         }
  560:                     }
  561:                   else if (cost_hi < best_cost_hi
  562:                            || (cost_hi == best_cost_hi
  563:                                && cost_lo < best_cost_lo))
  564:                     {
  565:                       /* Append at the end of the `first' list if there
  566:                          is no entry with this name.  */
  567:                       for (step = first; step != NULL; step = step->next)
  568:                         if (strcmp (result_set, step->result_set) == 0)
  569:                           break;
  570: 
  571:                       if (step == NULL)